Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

4. Alqoritmlərin mürəkkəbliyinin analizi

4.1. Alqoritmlərin mürəkkəbliyi. Mürəkkəblik haqqında teoremlər
Bəzən eyni bir məsələni həll etmək üçün müxtəlif alqoritmlərdən istifadə etmək imkanı olur. Bu halda bunlardan birini seçmək zərurəti yaranır. Münasib alqoritmi seçmək üçün alqoritmin praktikada istifadə imkanlarını qiymətləndirilməsi vacibdir ki, bunun üçün alqoritmin mürəkkəbliyi anlayışından istifadə olunur[6,11,22]. Alqoritmin mürəkkəbliyini müəyyən giriş informasiyanın həcmindən asılı funksiya kimi qiymətləndirmək olar. Məsələn, hanoy qülləsi məsələsinin mürəkkəbliyini f(n)=2ⁿ-1 düsturu ilə qiymətləndirirlər. Burada n disklərin sayını, f(n)-yerinə yetirilən əməliyyatların sayını göstərir. Deməli, alqoritmin mürəkkəbliyi məqsədə çatmaq üçün yerinə yetirilən elementar əməliyyatların sayı ilə əlaqələndirilir. Nəzərə alsaq ki, hər bir elementar əməliyyat üçün müəyyən zaman lazımdır, alqoritmin mürəkkəbliyini sərf olunan ümumi zamanla qiymətləndirmək məqsədəuyğundur. Bundan başqa alqoritmin mürəkkəbliyini kompüterin yaddaşının həcmindən istifadəyə görə qiymətləndirmək olar. Hər bir halda mürəkkəbliyi ifadə edən funksiyanın arqumenti “hesablama resursları” deyilən bir göstəricidir ki, bunun əsas komponentləri sərf olunan zaman və (və ya) kompüterin yaddaşının həcmidir.
Əgər hanoy qülləsinə aid məsələnin həlli zamanı bir diskin yerini dəyişmək üçün 1 saniyə lazım olarsa, onda 3 diskə aid hanoy qülləsi məsələnin həlli üçün 2³-1=7 saniyə sərf olunar. Lakin heç də hər alqoritmin mürəkkəbliyini hanoy qülləsi məsələsində olduğu kimi aşkar funksiya ilə qiymətləndirmək mümkün olmur. Bu halda alqoritmlərin mürəkkəbliyini dəqiq olmasa da təqribi üsulla qiymətləndirməyə çalışırlar, mürəkkəbliyin sinfini ifadə edən hipotetik f(n) funksiyasının yuxarı həddini (yaxud aşağı həddini, yaxud buların hər ikisini) qurmaqla bu işi yerinə yetirirlər.
Ənənəvi olaraq alqoritmlərin zaman mürəkkəbliyinin tədqiqi daha aktual məsələ hesab olunur. Aydındır ki, alqoritmin mürəkkəbliyi nəinki ilkin verilənlərin həcmindən, həmçinin onların düzülüşündən asılıdır. Düzülüş əlverişli olanda alqoritmin işi sürətlənir. Bu hala uyğun “alqoritmin ən yaxşı halda mürəkkəbliyi” anlayışı irəli sürülür. Əksinə, ilkin verilənlərin düzülüşü alqoritm üçün əlverişsiz olanda alqoritmin işi ləngiyir və bu hala uyğun “alqoritmin ən pis halda mürəkkəbliyi” anlayışı irəli sürülür. Hər iki üsul mürəkkəblik funksiyasının qrafikinin asimptotlarını qiymətləndirməyə imkan verir. Yuxarıda qeyd edilən bu iki mürəkkəbliyin riyazi gözləməsinə “alqoritmin orta mürəkkəbliyi” deyilir.
Asimptotik mürəkkəbliyin növləri. Fərz edək, f(n), g(n) – funksiyaları verilmişdir. Bunların arqumentləri natural ədədlər çoxluğunda, funksiyaların hər biri həqiqi ədədlər çoxluğunda qiymətlər alır.
Tərif 1: Əgər, elə m nömrəsi varsa ki, n m (n,m N) arqumentləri üçün k 0 ədədi olsun ki, bərabərsizliyi ödənilsin, onda deyirlər ki, f funksiyasının yuxarı asimptotu sabit vuruq dəqiqliyi ilə g(n) funksiyasıdır, bunu belə yazırlar: f(n) O(g(n)).
Bu mürəkkəbliyə bəzən “biq O notasiyası” deyilir[4 ].
Tərif 2: Əgər, elə m nömrəsi varsa ki, n m (n,m N) arqumentləri üçün k 0 ədədi olsun ki, bərabərsizliyi ödənilsin, onda deyirlər ki, f funksiyasının aşağı asimptotu sabit vuruq dəqiqliyi ilə g(n) funksiyasıdır, bunu belə yazırlar: f(n) o(g(n)).
Tərif 3: Əgər, elə m nömrəsi varsa ki, n m (n,m N) arqumentləri üçün k,k₁ 0 ədədləri olsun ki,
k₁ bərabərsizliyi ödənilsin, onda deyirlər ki, f funksiyasının aşağı və yuxarı asimptotu sabit vuruq dəqiqliyi ilə g(n) funksiyasıdır, bunu belə yazırlar: f(n) Ɵ (g(n)).
Göründüyü kimi, Ɵ qiymətləndirməsi verilmiş funksiyanın yuxarı və aşağı həddini eyni zamanda qiymətləndirə bilir.Onu da qeyd edək ki, mürəkkəbliliyin tərifində istifadə olunan k əmsalı onu göstərir ki, eyni bir mürəkkəbliliyə malik olan müxtəlif alqoritmlərin davamiyyəti bir-birindən xeyli fərqlənə bilər.Bəzən ədəbiyyatda f(n) o(g(n)), f(n) O(g(n)), f(n) Ɵ (g(n)) yazılışları əvəzinə müvafiq olaraq f(n) o(g(n)), f(n) O(g(n)), f(n) Ɵ (g(n)) yazılışlarından istifadə olunur. Məsələn, f(n)= o(nlog n) yazılışı onu göstərir ki, g(n)= nlog n. Bu sinfə dərəcəsi 1-dən böyük olan bütün polinomlar həm də, əsası 1-dən böyük olan bütün üstlü funksiyalar daxildir.Qeyd edək ki, f(n)= Ɵ(g(n)) şərti yalnız və yalnız o halda doğru olar ki, f(n)= O(g(n)) və f(n)= o(g(n)) şərtləri doğru olsun.
Alqoritmin praktiki mürəkkəbliliyini qiymətləndirmək nəzəri mürəkkəbliliyi qiymətləndirməkdən daha çətindir. Deməli, mürəkkəblik funksiyası əslində alqoritmin işləməsi üçün lazım olan zamanı dəqiq qiymətləndirməyə imkan verməsə də bu zamanın n-dən asılı dinamikasını qiymətləndirməyə imkan verir.
Alqoritmlərin mürəkkəbliyinin analizində daha çox baxılan məsələ “biq O notasiyası” hesab edilir.
Praktiki tədqiqatlarda alqoritmin mürəkkəbliyini limit anlayışından istifadə etməklə araşdırmaq daha əlverişlidir[7]. Tutaq ki, g(n) hər hansı məlum funksiya, f_A(n) isə A alqoritminin mürəkkəbliyini ifadə edən hipotetik funksiyadır.
Tərif 4: lim f_A(n)/g(n)= C =const olarsa, onda deyirlər ki,
^n→∞
f_A(n)-in yuxarı asimptotu g(n)-dir, bunu belə yazırlar: f_A(n)=

O(g(n)).
Misal. lim(5n³+n²+3)/n³=5.

^n→∞
Deməli, tərif 4-ə əsasən f_A(n)=5n³+n²+3 funksiyası O(n³) sinfinə aiddir. “O” xassəsinin mahiyyətini aşağıdakı kimi başa düşmək lazımdır: n→∞ olduqda f_A(n) və g(n) funksiyalarının hər biri özünü, sabit vuruğu ilə eyni sinifdən olan çətinlik dərəcəsi ilə ifadə edir.
Tərif 5: Əgər lim f_A(n)/g(n)=0 olarsa, onda deyirlər ki,
^n→∞
f_A(n) funksiyası o (g(n)) sinfinə aiddir. Bu sinfə aid olmaq onu göstərir ki, n→∞ olduqca f_A(n) funksiyası g(n) funksiyasına nisbətən sonsuz kiçik kəmiyyət kimi çıxış edir. Yəni A alqoritminin davamiyyəti g(n) funksiyasına nisbətən çox kiçik ədədlə ifadə oluna bilir.