Qaysi algoritmning vaqt murakkabligi O(n)?

Osonli murakkablikka ega algoritm O(n) bo'lsa, bu bajarilish vaqti yoki ishlatiladigan xotira kirish ma'lumotlarining n o'lchamiga mutanosib ravishda o'sadi. Bunday algoritmlarga misollar:

1. Massivda maksimal yoki minimal elementni topish: Boshqa barcha elementlarni bir marta o'tish kerak.

   # Maksimal elementni topish
   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. Chiziqli qidiruv: Tartiblanmagan ro'yxatda ma'lum bir elementni ketma-ket tekshirish orqali qidirish.

   // Chiziqli qidiruv
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Element topildi
           }
       }
       return -1; // Element topilmadi
   }
   

3. Ro'yxatdagi elementlarning chastotasini hisoblash: Buning uchun ro'yxatni bir marta o'tish, masalan, hash jadvali yoki lug'atdan foydalanish.

   // Chastotani hisoblash
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Oddiy nusxa olish: Asl massivning barcha elementlarini o'tib, yangi nusxa yaratish.

5. Massivdagi barcha elementlarning yig'indisini hisoblash: Bir marta o'tishni talab qiladi.

Ushbu barcha misollarda, operatsiyalar soni to'g'ridan-to'g'ri elementlar soniga proporsional bo'ladi.