Hangi algoritmanın zaman karmaşıklığı O(n)?

Bir algoritmanın zaman karmaşıklığı O(n) ise, çalışma süresi veya kullanılan bellek, giriş verilerinin boyutu n ile doğru orantılı olarak artar. Bu tür algoritmalara örnekler şunlardır:

1. Bir dizideki en büyük veya en küçük öğeyi bulma: Tüm öğeleri bir kez dolaşmak gerekir.

   # En büyük öğeyi bulma
   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. Doğrusal arama: Sıralanmamış bir listede belirli bir öğeyi ardışık tarama yoluyla bulma.

   // Doğrusal arama
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Öğe bulundu
           }
       }
       return -1; // Öğe bulunamadı
   }
   

3. Liste içindeki öğelerin sıklığını sayma: Bunun için listeyi bir kez dolaşmak gerekir, örneğin bir hash tablosu veya sözlük kullanarak.

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

4. Diziyi basitçe kopyalama: Orijinal dizinin tüm öğelerini dolaşarak yeni bir kopya oluşturma.

5. Dizideki tüm öğelerin toplamını hesaplama: Tüm öğeleri bir kez dolaşmayı gerektirir.

Tüm bu örneklerde, işlemlerin sayısı doğrudan işlenen verilerin öğe sayısıyla orantılıdır.