Big O və mürəkkəblik analizi
Big O alqoritmin işləmə vaxtının (və ya yaddaş sərfinin) giriş ölçüsü n böyüdükcə necə artdığını təsvir edir. Bu, saniyə ölçüsü deyil — artım sürətinin ölçüsüdür.
İki ayrı ölçü var:
- Time complexity — neçə əməliyyat icra olunur
- Space complexity — girişdən əlavə nə qədər yaddaş tutulur (input-un özü adətən sayılmır, buna auxiliary space deyilir)
Big O həmişə yuxarı hədd verir və n sonsuzluğa yaxınlaşdıqda dominant həddi saxlayır. Ona görə 3n² + 100n + 5000 sadəcə O(n²)-dir: n kifayət qədər böyük olanda n² qalan hər şeyi üstələyir.
| Mürəkkəblik | Ad | n = 1 000 000 üçün təxminən | Tipik nümunə |
|---|---|---|---|
| O(1) | sabit | 1 əməliyyat | massivdə indekslə oxumaq, hash map lookup |
| O(log n) | loqarifmik | ~20 əməliyyat | binary search, balanslı ağacda axtarış |
| O(n) | xətti | 1 000 000 | massivi bir dəfə gəzmək, maksimumu tapmaq |
| O(n log n) | xətti-loqarifmik | ~20 000 000 | merge sort, quick sort, dilin sort() metodu |
| O(n²) | kvadratik | 10¹² — praktiki olaraq mümkünsüz | iç-içə iki dövr, hər cütü müqayisə etmək |
| O(2ⁿ) | eksponensial | hesablanmaz | memoization-suz rekursiv fibonacci, bütün alt çoxluqlar |
Mürəkkəbliyi dövrdən necə çıxarmaq olar — sadə qaydalar:
- Ardıcıl bloklar toplanır:
O(n) + O(n) = O(2n) = O(n) - İç-içə dövrlər vurulur:
ndəfə dönən dövrün içindəndəfə dönən dövr =O(n²) - Hər addımda giriş yarıya bölünürsə —
O(log n) - Sabit əmsallar və kiçik hədlər atılır:
O(n/2)→O(n),O(n² + n)→O(n²)
Sabitlərin atılmasının səbəbi: Big O müxtəlif maşınlarda, müxtəlif dillərdə eyni qalan xassəni ölçür. Bir əməliyyatın 2 ns yoxsa 20 ns çəkməsi maşından asılıdır; girişi iki dəfə böyüdəndə vaxtın dörd dəfə artması isə alqoritmin öz xassəsidir.
Amma praktikada sabitlər var: n = 20 üçün O(n²) sadə həll çox vaxt O(n log n) mürəkkəb həlldən sürətlidir.
Best / average / worst case — eyni alqoritmin fərqli girişlərdə davranışı. Adətən worst case danışılır, çünki zəmanət odur.
Misal — sıralanmamış massivdə xətti axtarış: best O(1) (elə birinci element), average O(n/2) = O(n), worst O(n) (element yoxdur).
Amortized complexity — bir əməliyyatın uzun seriyada orta dəyəri. Dinamik massivə push: adətən O(1), amma tutum dolanda massiv iki dəfə böyüdülüb köçürülür — o tək əməliyyat O(n). Böyütmə getdikcə seyrək baş verdiyi üçün n push-un ümumi dəyəri O(n)-dir, yəni push amortized O(1)-dir.
Amortized ilə average-i qarışdırmayın: average ehtimala, amortized isə əməliyyatlar ardıcıllığının dəqiq hesabına söykənir.
İnterview məsləhəti. Demək olar hər kodlaşdırma sualının sonunda soruşurlar: "Bunun time və space complexity-si nədir?" Güclü cavabın quruluşu belədir: (1) rəqəmi de, (2) niyə-ni bir cümlə ilə əsaslandır, (3) daha yaxşı variant olub-olmadığını qeyd et. Məsələn: "O(n) time, çünki massivi bir dəfə gəzirəm; O(n) space, çünki hash map-də n açara qədər saxlaya bilərəm. n² həlli də var idi, hash map-lə n-ə endirdim."
Ən çox təkrarlanan səhvlər: space complexity-ni ümumiyyətlə demirlər; sort() çağırışını "pulsuz" sayıb O(n log n)-i saymırlar; iç-içə dövrləri toplayırlar (vurmaq əvəzinə); rekursiyada call stack-in yaddaşını unudurlar.