MÜHAZİRƏ 14 Alqoritmin mürəkkəbliyi Müxtəlif alqoritmləri müqayisə etdikdə onların mürəkkəbliyinin həll edilən məsələnin mürəkkəbliyindən necə asılı olduğu müəyyən etmək lazımdır. Hər hansı bir alqoritm üzrə 1000 ədədi nizamladıqda 1 saniyə, milyon ədədi nizamladıqsa isə 10 saniyə vaxt tələb olunduğu halda, başqa bir alqoritm üzrə həmin hesablamalara, uyğun olaraq, 2 və 5 saniyə tələb oluna bilər. Belə halda hansı proqramın yaxşı olması haqqında birmənalı fikir yürütmək mümkün olmur. Emaletmə sürəti nizamlanacaq verilənlərin növündən asılıdır. Alqoritmlərin məhsuldarlığı müxtəlif mürəkkəbliyə malik olan məsələlərin yerinə yetirilməsindən asılıdır. Alqoritmin sürətini kəmiyyətin tərtibinə uyğun qiymətləndirmək olar. Bu məqsədlə böyük 0(/(n)) funksiyasından istifadə edilir. Əgər n giriş verilənlərinin ölçüsü artdıqda alqoritmin yerinə yetirilmə vaxtı f(n) funksiyasının artma sürəti ilə artırsa, onda alqoritm O(/(n)) mürəkkəbliyinə malik olur.
Mürəkkəbliyin izahında tez-tez “Böyük O" funksiyasının aşağıdakı işarələrinə rast gəlirik:
/(n) = 0(1) -sabit;
/(n) = O(log(n)') -loqarifmik artım;
f(n) = 0(n) -xətti artım;
/(n) = 0(n * log(n)') -kvazi xətti artım;
/(n) = 0(nAm) -polinomial artım;
f(n) = 0(2An) -eksponensial artım.
Bu funksiyalarda A simvolu qüvvət üstünü bildirir, m isə ixtiyarı müsbət ədəddir.
/(n) = 0(g(ny) yazılışı onu müəyyən edir ki, ixtiyari böyük c=cl və n = N ədədləri üçün f(n) funksiyası g(n) funksiyasından daha yavaş artır. Başqa sözlə, c=cl və n>-N olduqda c*g(n)>=f(n). Burada, c hər hansı sabit, N isə giriş verilənlərinin sayıdır. Beləliklə, sadə dildə desək, O - alqoritmin yuxarıdan məhdudluğunu bildirir.
Alqoritmlərin hesablanması mürəkkəbliyini qiymətləndirmə növlərinin artma sırası ilə yerləşdirsək, aşağıdakı ardıcıllığı alarıq:
0(1), O(log n), 0(n), O(nlogn),O(n' k),O(k''n), 0(n!), 0(nAn). Bu siyahıda ilk sıralarda yerləşən mürəkkəbliyə uyğun alqoritmlər daha sürətlə işləyir.
Telefon məlumat kitabçası nümunəsində yuxarıdakı mürəkkəbliklərin bəzilərinə uyğun alqoritmlərin təsvirinə baxaq.
