O(n * log n) - kvaziloqarifmik mürəkkəblik.Fərz edək ki, Samirin əlinə bütün səhifələri qarışdırılmış məlumat kitabçası keçmişdir. O, əlbəttə, ağıllı olduğu üçün məlumat kitabçasının səhifələrini əlifba sırası ilə düzməyə qərar verəcək. Səhifədə birinci adamın soyadının birinci hərfi səhifəyə uyğun gəlir. Samir birinci səhifəni götürür və onu başqa cildə yerləşdirir. Sonra ikincini götürür və birinci adın birinci hərfindən asılı olaraq onu birincidən solda və ya sağda yerləşdirir. Kifayət qədər çox yığdıqdan sonra, o vərəqlər qalağının orta hissəsini açır, baxır və növbəti səhifənin solda və ya sağda olmasını müəyyənləşdirir. Müəyyən etdikdən sonra, daha kiçik qalaqlardan birini açır və həmin əməlləri təkrarlayır... ümumiyyətlə, yenə ikili axtarış alınır.
Misal olaraq sürətli nizamlamanı göstərmək olar.
0(nA2) - polinomial mürəkkəblik. Fərz edək ki, nəşriyyat nəyi isə qarışdırdı və telefon kitabında hər yazıya bir artıq rəqəm əlavə etdi və yazıların sayı qədər məlumat kitabçaları çap etdi.
Bu səhvi düzəltməyi Samirdən xahiş etdilər. O. n sayda məlumat kitabçalarını araşdırmalı və hər məlumat kitabçasının N sayda yazılarında bu son rəqəmin üstünü rəngləməlidir. Əgər biz bunu proqramlaşdırsaydıq, hər birində n iterasiya olmaqla bir-birinin daxilində olan 2 dövr alardıq. Nəticədə bu əməllər üçün n2 mürəkkəbliyini alırıq.
Müstəqil olaraq hər hansı alqoritmin mürəkkəbliyini qiymətləndirməyi bacarmaq üçün onun necə işləməsini dərk etmək lazımdır.
MÜHAZİRƏ 15 Alqoritmlərdə müxtəlif halların təhlili Alqoritmləri təhlil etdikdə üç müxtəlif halı araşdırmaq lazımdır:
• ən yaxşı hal;
• ən pis hal;
• orta hal.
Ən yaxşı hal. Alqoritmin ən yaxşı halı odur ki, bu alqoritm ən qısa vaxt ərzində yerinə yetirilir. Bu zaman verilənlər yığımı elə qiymətlər kombinasiyasından ibarət olur ki, alqoritm çox az əməliyyat yerinə yetirir. Əgər biz axtarış alqoritmini təhlil etsək, aşkar edərik ki, elə verilənlər yığımı ən yaxşı olacaq ki, orada axtarılan element alqoritmin birinci yoxlanılan xanasında yerləşsin. Belə alqoritmin mürəkkəbliyindən asılı olmayaraq yalnız bir müqayisə əməliyyatı yerinə yetiriləcəkdir və alqoritm həmişə sabit vaxt ərzində işini başa çatdıracaqdır. Belə alqoritmlər çox sadə olduğu üçün, adətən, alqoritmin ən yaxşı halını tədqiq etməyə ehtiyac qalmır.
