Big O

İndiyə qədər biz alqoritmlərin sürətini ölçmək üçün addımların sayına baxırdıq. Ancaq hər alqoritm üçün dəqiq addım sayını əvvəlcədən müəyyən etmək mümkün deyil.

Məsələn, linear search alqoritmi üçün: əgər array-də 30 element varsa, axtarış 30 addım çəkəcək; 100 element varsa, 100 addım tələb olunacaq. Ümumi şəkildə ifadə etsək, array-də N element olduqda, linear search maksimum N addım atacaq.

Kompüter alimləri alqoritmlərin zaman mürəkkəbliyini ifadə etmək və başqalarına daha rahat izah etmək üçün Big O Notation adlı bir konsepsiya tətbiq ediblər. Bu anlayış, kodun effektivliyini kateqoriyalara ayırmağa və müqayisə etməyə kömək edir.

Big O və Linear search

Big O-nu linear search (xətti axtarış) üçün tətbiq edək. Yuxarıda qeyd etdiyimiz kimi, linear search N element üçün maksimum N addım atır. Bunu Big O ilə ifadə etmək üçün əsas sualı verək: N element varsa, alqoritm neçə addım atacaq? Cavab: O(N)

Sualın cavabı, Big O ifadəmizin mötərizələri içərisindədir. O(N) deyir ki, alqoritm N addım atacaq. O(N) olan bir alqoritm, linear time (xətti zaman) olaraq da bilinir.

İndi isə Big O-nu standart bir array-dən oxuma əməliyyatına tətbiq edək. Niyə Data Strukturu Vacibdir? bölməsində öyrəndiyimiz kimi, array-dəki bir elementi oxumaq üçün, onun ölçüsündən asılı olmayaraq, yalnız bir addım atılır.

Bunu Big O ilə ifadə etmək üçün yenə əsas sualı veririk: Array-də N element varsa, bir elementi oxumaq neçə addım çəkir? Cavab: 1 addım

Bu, O(1) olaraq yazılır və constant time (sabit zaman) kimi tanınır. Yəni, elementi oxumaq üçün tələb olunan vaxt, array-in ölçüsündən asılı deyil və həmişə eyni qalır.

O(1)

Bura qədər O(N) və O(1) gördük.

İndi isə başqa bir nümunəyə baxaq: Təsəvvür edin ki, bizim bir array-imiz var və bu array-dəki elementlərin sayından (N) asılı olmayaraq, alqoritmimiz həmişə 5 addım atır. Bu halda, bu alqoritimi Big O ilə necə ifadə edə bilərik?

Əgər cavabınız O(5)-dirsə, bu səhvdir. Doğru cavab O(1)-dir.

Nə üçün O(1)?

Big O Notation-un əsas məqsədi, məlumat artdıqca alqoritmin performansının necə dəyişəcəyini göstərməkdir. Bu baxımdan, O(1) və O(5) arasında mahiyyət etibarilə heç bir fərq yoxdur. Hər iki halda, alqoritmin addımlarının sayı sabit qalır və məlumatın ölçüsündən (N) asılı olmur.

Məlumat artdıqca qrafikdə necə addımların sayının artdığına baxaq:

Burada O(N) alqoritm üçün data artdıqca qrafikdə diaqonal xətt alınır, çünki məlumat artdıqca daha çox addım atılır. O(1) də isə qrafikdə üfüqi xətt alınır, çünki məlumatın ölçüsündən (N) asılı olmayaraq addımların sayı sabit qalır.

Linear search həmişə O(N) olmaya bilər. Əlbəttdə axtardığımız data array-in sonunda yerləşirsə, alqoritm N addım atacaq və O(N) olacaq. Amma əgər ilk indeksdədirsə, yalnız 1 addım atacaq və O(1) olacaq.Buna görə də deyə bilər ki, ən yaxşı ssenaridə Linear Search O(1), ən pis ssenaridə isə O(N) olur.

Big O Notation həm ən yaxşı, həm də ən pis halları təsvir edə bilər, lakin ümumiyyətlə, ən pis hal (worst-case scenario) üçün istifadə olunur. Məsələn, linear search (xətti axtarış) üçün ən yaxşı halda zaman mürəkkəbliyi O(1) ola bilər lakin Big O Notation-da bu alqoritm O(N) kimi deyilir. Bunun səbəbi, ən pis halın nəzərə alınmasıdır.

“Pessimistic” yanaşma faydalı bir vasitədir: bir alqoritmin ən pis halda nə qədər səmərəsiz ola biləcəyini bilmək, bizə ən pis vəziyyətə hazırlıqlı olmaq imkanı verir və qərar qəbul edərkən böyük təsir göstərə bilir.

Məsələn, linear search üçün ən pis halda O(N) addım tələb olunduğunu bilmək, böyük məlumat dəstləri ilə işləyərkən bu alqoritmin performansının necə dəyişəcəyini proqnozlaşdırmağa kömək edir. Bu, daha effektiv alqoritmlər seçməyimizə və sistemin performansını optimallaşdırmağımıza imkan yaradır.

Big O və Binary search

Biz öyrəndik ki, sırali array-lərdə binary search daha effektivdir. İndi isə binary search Big O ilə necə ifadə olunduğuna baxaq.

Binary Search-u O(1) ilə göstərə bilmərik, çünki data böyüdükcə addım sayı da artır. O(N) ilə də göstərə bilmərik, çünki addım sayı data sayından azdır. Məsələn, binary search 100 element üçün cəmi 7 addım atır.

Deməli, binary search O(1) ilə O(N) arasında bir yerdə olmalıdır.

Binary Search, Big O ilə O(log N) kimi göstərilir.

O(log N), hər dəfə məlumat ikiqat artırıldıqda bir addım artan alqoritmi təsvir etməyin Big O yoludur. Binary Search də belə işləyir: məlumatın ölçüsü ikiqat artdıqca yalnız bir addım daha artır.

İndiyə kimi öyrəndiyimiz alqoritmalar effektlilik baxımından belə düzülə bilər(ən yaxşıdan ən pisə doğru düzülmüşdür.):

• O(1)
• O(log N)
• O(N)

Loqarifma

Log, logaritmanın qısaltmasıdır.

Loqarifmlər, eksponentlərin tərsidir. Eksponentlərin nə olduğunu anlamaq üçün bir nümunəyə baxaq:

2³ = 2 × 2 × 2.

Burada 2 “əsas” ədəd, 3 isə “eksponent”dir. Bu, 2-nin öz-özünə üç dəfə vurulması deməkdir və nəticədə 8 alınır, yəni 2³= 8.

Logaritm isə bunun tərsini ifadə edir. log₂ 8, “8-i əldə etmək üçün 2-ni neçə dəfə öz-özünə vurmaq lazımdır?” sualına cavab verir.

2-ni 3 dəfə vurduqda 8 alınır, buna görə də log₂ 8 = 3.

Başqa bir nümunəyə baxaq:

2⁶= 2 × 2 × 2 × 2 × 2 × 2 = 64.

2-ni 6 dəfə vurduqda 64 alınır. Bunun logaritmik ifadəsi log₂ 64 = 6 şəklində yazılır. Bu da göstərir ki, 2-ni 6 dəfə öz-özünə vurduqda 64 əldə olunur.

Bunu başqa bir şəkildə də düşünə bilərik: Əgər 8-i 2-yə bölüb 1-ə çatana qədər davam etsəydik, neçə dəfə bölməli olardıq?

8 ÷ 2 = 4 4 ÷ 2 = 2 2 ÷ 2 = 1

Burada 8-i 1-ə çatana qədər 3 dəfə 2-yə böldük. Bu da göstərir ki, 8-in 2 əsasına görə logaritmsı 3-dür, yəni log₂ 8 = 3.

Eyni qayda ilə, 64-ü də 2-yə bölərək yoxlayaq:

64 ÷ 2 = 32 32 ÷ 2 = 16 16 ÷ 2 = 8 8 ÷ 2 = 4 4 ÷ 2 = 2 2 ÷ 2 = 1

Burada da 64-ü 1-ə çatana qədər 6 dəfə böldük. Bu o deməkdir ki, log₂ 64 = 6

O(log N) Açıqlaması

Biz O(log N) deyərkən əslində O(log₂N) nəzərdə tuturuq.

Əsas sualımızı xatırlayaq: N element varsa, alqoritm neçə addım atacaq? O(log N) demək, N element varsa, log₂N addım atacaq deməkdir.

Yəni 8 elementimiz varsa, bu 3 addım atacaq, çünki: log₂ 8 = 3

Bunu başqa cür necə fikirləşə bilərdik 8-ni neçə dəfə 2-yə bölsək 1 olar 3 dəfə. Binary search tam olaraq belə işləyir: bölə-bölə gedirik ta ki bir element qalanadək.

İndi isə bir koda nümunsinə baxaq və onun BigO zaman kompleksliyini təxmin edək

let arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

function printNumbers(numbers) {
  for (let i = 0; i < numbers.length; i++) {
    console.log(numbers[i]);
  }
}

printNumbers(arr);

Yuxarıdakı kodun Big O efficiency (zaman kompleksliyi) nədir?

Bu kodun Big O zaman kompleksliyi O(N)-dir. Çünki for dövrü array-dəki hər bir elementə bir dəfə baxır. Bu səbəbdən, element sayı artdıqca, işləmə vaxtı da xətti şəkildə artır.