Big O notasyonu: əsas konsepsiyalar

2.1 Big O notasiyasının tərifi.

Big O notasiyası — riyazi notasiya, hansı ki, alqoritmin giriş məlumatlarının ölçüsündən asılı olaraq icra müddətinin və ya resurs istifadəsinin yuxarı sərhədini təsvir etmək üçün istifadə olunur. Bu, alqoritmin necə yaxşı ölçülə biləcəyini və onun performansının məlumatların həcmi artdıqca necə dəyişdiyini anlamada kömək edir.

Big O notasiyası alqoritmin ən əhəmiyyətli cəhətlərinə fokuslanır, sabitləri və az əhəmiyyətli terminləri nəzərə almadan, alqoritmin uzunmüddətli davranışına diqqət etməyə imkan verir.

Əsas notasiyalar:

O(1) — Konstant mürəkkəblik:

• Alqoritmin iş müddəti giriş məlumatlarının ölçüsündən asılı deyil.
• Misal: massiv elementinə indekslə daxil olmaq.

O(n) — Xətti mürəkkəblik:

• Alqoritmin iş müddəti giriş məlumatlarının ölçüsündən xətti asılıdır.
• Misal: massivdəki bütün elementləri sadəcə sıralamaq.

O(log n) — Logaritmik mürəkkəblik:

• Alqoritmin iş müddəti giriş məlumatlarının ölçüsü artdıqca logaritmik olaraq artır.
• Misal: sıralanmış massivdə binary search.

O(n^2) — Kvadrat mürəkkəblik:

• Alqoritmin iş müddəti giriş məlumatlarının ölçüsündən kvadrat asılıdır.
• Misal: bubble sort, insertion sort.

O(2^n) — Eksponensial mürəkkəblik:

• Alqoritmin icra müddəti giriş məlumatlarının ölçüsündən eksponensial olaraq asılıdır.
• Misal: knapsack probleminin tam kombinasiyalarla həlli.

2.2 Big O notasiya interpretasiyası.

Big O ni necə interpretasiya və istifadə etmək olar?

Konstantaları və az əhəmiyyətli termləri gözardı etmək:

Big O funksiyanın artım qaydasını təsvir edir, konstantaları və az əhəmiyyətli termləri nəzərə almır. Məsələn, O(2n) və O(3n) O(n) kimi interpretasiya edilir.

Alqoritmlərin müqayisəsi:

Big O alqoritmləri asimptotik effektivliyinə görə müqayisə etməyə imkan verir. Məsələn, O(n log n) ilə olan alqoritm, çox böyük verilənlər üçün O(n^2) ilə olan alqoritmdən daha səmərəlidir.

Ən pis halın analizi:

Big O adətən alqoritmin ən pis iş vaxtını analiz etmək üçün istifadə olunur, bu, maksimum mürəkkəbliyini qiymətləndirməyə imkan verir.

Konstantaları gözardı etmək.

Konstantaları və az əhəmiyyətli termləri gözardı etmək

Nümunə 1:

İki funksiyanı nəzərdən keçirək:

• f(n) = 3n + 2
• g(n) = 5n + 1

Hər iki funksiyanın xətti mürəkkəbliyi var, çünki hər funksiyada dominant termin n-dir. Buna görə də, hər iki funksiya O(n) kimi interpretasiya olunur, koeffisentlərdə və əlavə termlərdəki fərqlərə baxmayaraq.

Nümunə 2:

İki funksiyanı nəzərdən keçirək:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

Hər iki funksiyanın kvadratik mürəkkəbliyi var, çünki dominant termin n^2-dir. Hər iki ifadə O(n^2) kimi interpretasiya olunur, digər termlərdəki və koeffisentlərdəki fərqlərə baxmayaraq.

2.3. Alqoritmlərin müqayisəsi

1. Çox böyük verilənlər həcmlərində alqoritmlərin müqayisəsi

Nümunə 1:

• Alqoritm A zaman mürəkkəbliyinə malikdir O(n^2).
• Alqoritm B zaman mürəkkəbliyinə malikdir O(n log n).

Kiçik n qiymətləri üçün, Alqoritm A daha sürətli işləyə bilər kiçik sabitlərə görə, amma böyük n qiymətləri üçün, Alqoritm B əhəmiyyətli dərəcədə daha sürətli olacaq, çünki onun artımı logaritmikdir, kvadratik deyil.

Nümunə 2:

• Alqoritm X zaman mürəkkəbliyinə malikdir O(n).
• Alqoritm Y zaman mürəkkəbliyinə malikdir O(1).

Alqoritm Y həmişə daha sürətli olacaq, n ölçüsündən asılı olmayaraq, çünki O(1) alqoritmin icra müddətinin giriş verilənlərinin ölçüsündən asılı olmadığını ifadə edir.

2. Ən pis halda analiz

Nümunə 1:

"Bubble Sort" alqoritmi ən pis halda zaman mürəkkəbliyinə malikdir O(n^2), yəni massiv tərsinə sıralanmışdır. Bu o deməkdir ki, massivdəki hər element üçün müqayisə və mümkün digər elementlərlə mübadilə tələb olunacaq.

Nümunə 2:

İkili axtarış alqoritmi ən pis halda zaman mürəkkəbliyinə malikdir O(log n). Bu o deməkdir ki, hətta ən pis halda belə, bir elementin tapılması üçün lazım olan addımların sayı massiv ölçüsündən logaritmik asılı olacaq, bu isə çox səmərəlidir.

3. Performansa və miqyaslana bilənliyə təsir

Nümunə 1:

Əgər bizdə verilənləri emal etmək üçün iki alqoritm varsa, biri zaman mürəkkəbliyinə malikdir O(n^2), digəri isə O(n log n), və biz verilənlərin ölçüsünü 1000 elementdən 10,000 elementə artırırıqsa, performans fərqi əhəmiyyətli dərəcədə hiss olunacaq.

• O(n^2) mürəkkəbliyinə malik alqoritm 10,000 element üçün təxminən 100,000,000 əməliyyat yerinə yetirəcək.
• O(n log n) mürəkkəbliyinə malik alqoritm 10,000 element üçün təxminən 40,000 əməliyyat yerinə yetirəcək.

Nümunə 2:

Götürək ki, alqoritm O(2^n) mürəkkəbliyinə malikdir. Əgər biz giriş verilənlərinin ölçüsünü 10-dan 20 elementə artırırıqsa, əməliyyatların sayı eksponensial olaraq artacaq.

• n = 10 üçün: 2^10 = 1024 əməliyyat.
• n = 20 üçün: 2^20 = 1,048,576 əməliyyat.

Bu göstərir ki, eksponensial mürəkkəblik böyük n dəyərləri üçün necə tezliklə qeyri-praktik olur.