Ən pis hal. Ən pis halın araşdırılması çox vacibdir, çünki, bu halda proqramın icrası maksimal vaxt tələb edir. Ən pis halı tədqiq etdikdə verilənlərin elə yığımını tapmaq lazımdır ki, proqram ən çox iş görsün. Axtarış alqoritmi üçün belə verilənlər yığımı axtarılan elementin siyahının sonunda olduğu haldır. Ən pis halın təhlili nəticəsində proqramın iş vaxtının ən yuxarı qiyməti müəyyən edilir.
Orta hal. Orta vəziyyətin təhlili ən mürəkkəb haldır, çünki, bu zaman külli miqdarda müxtəlif əməliyyatlar araşdırılır. Təhlilin əsasını ilkin verilənlər yığımının müəyyən qruplara bölünərək təhlil edilməsi təşkil edir. İkinci addımda verilənlərin hansı qrupa aid olması ehtimalı hesablanır. Üçüncü addımda alqoritmin hər bir qrupda işləməsi vaxtı hesablanır. Bu vaxt bütün qruplar üçün eyni olmalıdır. Orta iş vaxtı
düsturu ilə hesablanır. Burada, n - ilkin verilənlərin ölçüsü, m - qrupların sayı, p - verilənlərin z-ci qrupa daxil olması ehtimalı, t isə z-ci qrupda alqoritmin yerinə yetirilmə vaxtıdır. Bəzi hallarda ilkin verilənlərin qrupa daxil olması ehtimalı eyni qəbul edilir. Məsələn, qrupların sayı 5 olduqda verilənlərin l-ci, 2-ci və s. qruplara aid olması ehtimalı eyni, yəni, 0.2 olacaqdır. Bu halda orta iş vaxtı aşağıdakı düsturla hesablanır:
Dostları ilə paylaş: |
