Որ ալգորիթմն ունի գծային բարդություն O(n)?

Յուրաքանչյուր ալգորիթմի գծային բարդությունը O(n) նշանակում է, որ գործարկման ժամանակը կամ օգտագործված հիշողությունը պրոպորցիոնալ է մուտքային տվյալների n չափի հետ։ Այդպիսի ալգորիթմների օրինակներ են՝

1. Մաքսիմալ կամ մինիմալ տարր գտնել զանգվածում: Պետք է անցնել բոլոր տարրերով զանգվածը մեկ անգամ։

   # Մաքսիմալ տարր գտնել
   def find_max(arr):
       if not arr:
           return None
       max_val = arr[0]
       for element in arr:
           if element > max_val:
               max_val = element
       return max_val
   

2. Գծային որոնում: Որոնում է որոշակի տարր ոչ դասավորված ցուցակում՝ սեկվենցիոն անցումով։

   // Գծային որոնում
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Տարրը գտնվեց
           }
       }
       return -1; // Տարրը չգտնվեց
   }
   

3. Տարրերի հաճախականության հաշվարկ: Դրա համար անհրաժեշտ է մեկ անգամ անցնել ցուցակով՝ օրինակ, հեշ-թաբլթա կամ բառարան օգտագործելով։

   // Հաճախականության հաշվարկ
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Պարզ պատճենահանում: Օրիգինալ զանգվածի բոլոր տարրերով անցնելով՝ նոր պատճեն ստեղծել։

5. Բոլոր տարրերի գումարը հաշվարկել: Դա պահանջում է մեկ անգամ անցնել բոլոր տարրերով։

Այս բոլոր օրինակներում գործողությունների քանակը ուղղակիորեն համեմատական է մշակվող տվյալների տարրերի թվին։