MüNDƏrcat mühaziRƏ 1 Verilənlər. Alqoritmlər və verilənlərin strukturu

0(1) sabit mürəkkəbliyindən başlayaq. Təsəvvür edək ki, tələbə Samir telefon məlumat kitabçasında qrup yoldaşı Kamilin nömrəsi yazılmış səhifəni qatlamışdır. Bu, Kamilin nömrəsini orta hesabla sabit vaxt ərzində axtarmağa imkan verir, çünki, burada nömrələrin miqdarından düz asılılıq yoxdur və ya o, o qədər kiçikdir ki, onu nəzərə almamaq olar. Niyə orta hesabla? Çünki ona bu səhifədə müəyyən sayda digər yazıları nəzərdən keçirmək lazım olmuşdur ki, onu da kiçik olduğu üçün nəzərə almamaq olar.
Misal kimi bir “zənbildə” bir obyektin axtarışını göstərmək olar.
0(log n) — loqarifmik mürəkkəblik. Loqarifmik mürəkkəblik nisbətən çətindir. Təsəvvür edək ki, Samir Kamillə təzəcə tanış olmuşdur. O, onun soyadını bilir. Bəs indi Kamilin nömrəsi olan səhifəni o necə axtaracaqdır? O. məlumat kitabçasını ortadan açır və hər hansı bir yazıya baxır və görür ki, burada soyadın baş hərfi Kamilin soyadındakı baş hərfdən əvvəldə yerləşir. Deməli, Kamilin nömrəsi məlumat kitabçasının ikinci yarısındadır. İndi o, məlumat kitabçasının Kamilin nömrəsi olan tərəfindən vərəqlər qalağını götürür və onun təxminən orta hissəsini açır və s. Beləliklə, binar (ikili) axtarış alınır. Ona lazım olacaq müqayisələrin miqdarı məlumat kitabçasında səhifələrin miqdarının 2 əsasa görə loqarifminə bərabər olacaqdır. Əgər bu məlumat kitabçasına 10000 nömrədən ibarət daha 100 səhifə əlavə etsək də, müqayisələrin miqdarı kəskin artmayacaqdır. Bu, binar ağacı xatırladır ki, burada ən aşağı səviyyədəki obyekti tapmaq üçün ağacın hündürlüyünə bərabər sayda və ya yazıların ümumi sayının iki əsasdan loqarifmi qədər müqayisələr etmək lazımdır. Əgər məlumat kitabçasında 1000 səhifə olarsa, onda təxminən 10, 4000 səhifə olduqda isə təxminən 12 müqayisə etmək lazımdır. Göründüyü kimi, səhifələrin sayı 4 dəfə də artdıqda müqayisələrin sayı yalnız 2 vahid qədər artır.
Misal kimi binar ağacda axtarışı göstərə bilərik. Burada müqayisələrin miqdarı təxminən ağacın hündürlüyünə bərabər olur (əgər ağac, əlbəttə, tarazlaşdırılmışdırsa). O(n) - xətti mürəkkəblik. Burada izahat daha sadədir. Tutaq ki, bizim telefon məlumat kitabçamızda bütün nömrələr təsadüfi qaydada yerləşmişdir. Onda ehtimal ki, Samir çox uzun müddət ərzində kitabda bütün nömrələri korkoranə araşdıraraq Kamilin nömrəsini axtaracaqdır. Nə qədər çox axtararsa, o, əmin olacaq ki, belə səylər əziyyətə dəyməz. Əgər nömrələrin sayını 4 dəfə artırsaq, onda Samir də 4 dəfə daha çox vaxt sərf edəcək.
Bu mürəkkəbliyə aid misal kimi siyahıda qiymətə görə lazım olan yazının axtarışını göstərə bilərik.