Hansı algoritm lineyar mürəkkəbliyə malikdir O(n)?

Bir algoritmin vaxt mürəkkəbliyi O(n) isə, bu, icra vaxtının və ya istifadə olunan yaddaşın giriş məlumatlarının n ölçüsü ilə proporsional şəkildə artdığını göstərir. Belə algoritmlərə nümunələr:

1. Massivdə maksimum və ya minimum elementi tapmaq: Bu, bütün elementləri bir dəfə keçməyi tələb edir.

   # Maksimum elementi tapmaq
   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. Xətti axtarış: Sıralanmamış siyahıda müəyyən bir elementi ardıcıl yoxlama yolu ilə tapmaq.

   // Xətti axtarış
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Element tapıldı
           }
       }
       return -1; // Element tapılmadı
   }
   

3. Siyahıdakı elementlərin tezliyini saymaq: Bunun üçün siyahını bir dəfə keçmək, məsələn, hash cədvəli və ya sözlük istifadə etmək lazımdır.

   // Tezlik sayımı
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Sadə surət çıxarma: Orijinal massivdəki bütün elementləri keçərək yeni surət yaratmaq.

5. Massivdəki bütün elementlərin cəmini hesablamaq: Bu, bütün elementləri bir dəfə keçməyi tələb edir.

Bütün bu nümunələrdə, əməliyyatların sayı işlənən məlumatların element sayına birbaşa proporsionaldır.