Big O Notasiyası

11.1 Big O Notasiyasının Tərifi

Big O Notasiyası — riyazi bir notasiya olaraq, alqoritmin işləmə vaxtının və ya resurs tələbinin giriş məlumatlarının ölçüsündən asılı olaraq yuxarı həddini təsvir etmək üçün istifadə olunur. Bu, alqoritmin nə qədər yaxşı genişləndiyini və məlumat həcminin artması ilə performansının necə dəyişdiyini müəyyən etməyə kömək edir.

Big O Notasiyası alqoritmin əhəmiyyətli aspektlərinə fokuslanır, sabitlər və daha az əhəmiyyətli hissələri nəzərə almır, beləliklə alqoritmin uzunmüddətli davranışına diqqət yetirməyə imkan verir.

Əsas notasiyalar:

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

• Alqoritmin işləmə vaxtı giriş məlumatlarının ölçüsündən asılı deyil.
• Nümunə: massivdən indeks üzrə elementə giriş.

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

• Alqoritmin işləmə vaxtı giriş məlumatlarının ölçüsü ilə xətti şəkildə artar.
• Nümunə: massivdəki bütün elementləri sadə şəkildə keçmək.

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

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

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

• Alqoritmin işləmə vaxtı giriş məlumatlarının ölçüsündən kvadratik şəkildə asılıdır.
• Nümunə: bubble sort, insertion sort.

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

• Alqoritmin işləmə vaxtı giriş məlumatlarının ölçüsündən eksponensial şəkildə asılıdır.
• Nümunə: tam şəkildə knapsack probleminin həlli.

Qeyd. Binary search, bubble sort və "knapsack problemi" haqqında daha ətraflı məlumatı növbəti mühazirələrdə əldə edəcəksiniz.

11.2 Big O notasıyasının izah edilməsi

Big O notasıyasını necə anlamaq və istifadə etmək olar?

Konstantları və daha az əhəmiyyətli üzvləri nəzərə almamaq: Big O funksiyanın artma dərəcəsini təsvir edir, konstantları və daha az əhəmiyyətli üzvləri nəzərə almır. Məsələn, O(2n) və O(3n) O(n) kimi izah edilir.

Alqoritmlərin müqayisəsi: Big O alqoritmləri onların asimptotik effektivliyinə görə müqayisə etməyə imkan verir. Məsələn, O(n log n) dəyəri olan alqoritm O(n^2) dəyəri olan alqoritmdən daha effektivdir, xüsusilə çox böyük məlumat həcmləri üçün.

Ən pis halın analizi: Big O adətən alqoritmin ən pis halda icra müddətini təhlil etmək üçün istifadə olunur, bu da maksimum mürəkkəbliyi qiymətləndirməyə imkan verir.

Konstantları nəzərə almamaq

Konstantların və daha az əhəmiyyətli üzvlərin nəzərə alınmaması ilə bağlı nümunələrə baxaq:

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 bir funksiyanın dominant elementi n-dir. Buna görə, hər iki funksiya O(n) kimi izah edilir, fərqli koeffisientlərə və əlavə elementlə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 element n^2-dir. Hər iki ifadə O(n^2) kimi izah edilir, fərqli üzvlər və koeffisientlər olsa da.

11.3. Alqoritmlərin müqayisəsi

1. Alqoritmlərin çox böyük verilənlər həcmi üzrə müqayisəsi

Misal 1:

• A Alqoritminin vaxt mürəkkəbliyi O(n^2).
• B Alqoritminin vaxt mürəkkəbliyi O(n log n).

Kiçik n dəyərləri üçün A alqoritmi kiçik sabitlər səbəbindən daha sürətli işləyə bilər, amma böyük n dəyərlərdə B alqoritmi xeyli sürətli olacaq, çünki onun artımı logaritmikdir, kvadrat deyil.

Misal 2:

• X Alqoritminin vaxt mürəkkəbliyi O(n).
• Y Alqoritminin vaxt mürəkkəbliyi O(1).

Y alqoritmi həmişə daha sürətli olacaq, n-in ölçüsündən asılı olmayaraq, çünki O(1) alqoritmin iş vaxtının giriş verilənlərinin ölçüsündən asılı olmadığını göstərir.

2. Ən pis vəziyyətin analizi

Misal 1:

Bubble sort növləmə alqoritminin ən pis vəziyyətdə vaxt mürəkkəbliyi O(n^2)-dir, məsələn, massiv tərsinə düzülüb. Bu o deməkdir ki, massivin hər bir elementi üçün digər hər bir elementlə müqayisə və bəlkə də dəyişmə tələb olunacaq.

Misal 2:

Binary search alqoritminin ən pis vəziyyətdə vaxt mürəkkəbliyi O(log n)-dir. Bu, o deməkdir ki, hətta ən pis vəziyyətdə belə elementi tapmaq üçün lazım olan addımların sayı massivin ölçüsündən logaritmik asılılıqla dəyişəcək və bu çox effektivdir.

3. Performansa və genişlənməyə təsiri

Misal 1:

Deyək ki, verilənləri emal etmək üçün iki alqoritmimiz var, biri vaxt mürəkkəbliyi O(n^2) ilə, digəri isə O(n log n) ilə çalışır, və verilənlərin ölçüsünü 1000 elementdən 10 000 elementə qədər artırırıqsa, performansdakı fərq xeyli hiss olunacaq.

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

Misal 2:

Gəlin O(2^n) ilə işləyən bir alqoritmə baxaq. Əgər giriş verilənlərinin ölçüsünü 10 elementdən 20 elementə artırırıqsa, əməliyyatların sayı eksponensial olaraq artır.

• n = 10: 2^10 = 1024 əməliyyat.
• n = 20: 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-praktiki olur.

1

Опрос

Məlumat strukturları,  52 уровень,  4 лекция

недоступен

Məlumat strukturları

Məlumat strukturları

Открыть