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

. MÜHAZİRƏ 13
Alqoritmlərin təhlili
Təhlil nədir?
Eyni bir məsələni bir neçə alqoritmlə həll etmək olar. Hər bir alqoritmin səmərəliliyi müxtəlif xarakteristikalarla təsvir olunur. Alqoritmin səmərəli olub-olmadığını araşdırmazdan əvvəl, bu alqoritmin qoyulmuş məsələni düzgün həll edib-etməməsini sübut etmək lazımdır. Əgər alqoritm məsələni düzgün həll etmirsə, onun səmərəliyinin mənası itir. Alqoritmi təhlil edildikdə onun yerinə yetirilməsi üçün lazım olan vaxtın miqdarı müəyyən edilir. Belə vaxt dedikdə alqoritmin dəqiq olaraq neçə saniyəyə və ya dəqiqəyə (saata) yerinə yetirilməsi deyil, alqoritmin yerinə yetirilməsi üçün təxminən neçə əməliyyatın yerinə yetirilməsi nəzərdə tutulur. Əməliyyatların sayı dolayı yolla elə alqoritmin nisbi yerinə yetirilmə vaxtını müəyyən edir. Ona görə də alqoritmin hesablama mürəkkəbliyinə bəzən vaxt deyirlər. Alqoritmin yerinə yetirilməsinin faktiki saniyələrinin miqdarı və ya əməliyyatların faktiki sayı alqoritmin təhlilində bir o qədər də əhəmiyyət kəsb etmir. Bunun əvəzinə bizi daha çox konkret alqoritmin əməliyyatlarının sayının ilkin verilənlərin ölçüsündən asılılığı maraqlandırır. Biz iki alqoritmi əməliyyatların sayının artma sürəti ilə müqayisə edə bilərik. Məhz artma sürəti alqoritmlərin təhlilində əsas rol oynayır, məsələn, ilkin verilənlərin kiçik qiymətlərində A alqoritmi ola bilər ki, B alqoritminə nisbətən daha az əməliyyat tələb etsin, lakin ilkin verilənlərin həcmi artdıqda bu mənzərə tamamilə dəyişə bilər. Qeyd edək ki, yalnız eyni bir məsələni həll edən müxtəlif alqoritmlər müqayisə edilə bilər. Ona görə də heç vaxt nizamlama alqoritmi ilə, məsələn, matrislərin vurulması alqoritmini müqayisə etmək olmaz, yalnız müxtəlif nizamlama alqoritmləri bir-biri ilə müqayisə edilə bilər. Müqayisə nəticəsində saniyələrin miqdarını və ya computer dövrlərinin sayını dəqiq hesablayan düsturlar axtarılmır. Bunun heç mənası da yoxdur. Belə ki, bu halda gərək kompüterin tipi də nəzərə alınsın.
Alqoritmlərin təhlilinin digər üsulu alqoritmin Pascal, C++, Java, C#, Python kimi yüksək səviyyəli dillərdə və ya ümumi psevdokodda yazılmasını nəzərdə tutur. Əgər psevdokod bütün alqoritmlər üçün ümumi olan idarəetmənin əsas strukturlarını reallaşdırırsa, onda onun xüsusiyyətləri əhəmiyyətli rol oynamır, for və ya while kimi dövrlər, if, case və ya switch şəklində budaqlanma mexanizmi istənilən proqramlaşdırma dilində mövcuddur və istənilən belə dil bizim məqsədimizə uyğun gələcək. Hər dəfə biz bir konkret alqoritmə baxacağıq, burada bir funksiya və ya proqramın fraqmenti iştirak edəcək və buna görə də yuxarıda sadaladığımız dillər heç bir rol oynamır. Ona görə də biz alqoritmləri təhlil etdikdə bəzi hallarda psevdokodlardan istifadə edəcəyik.
Alqoritmlərin mürəkkəbliyinin zəruriliyini bilmək üçün misala baxaq. Müasir kompüterlər çox böyük sürətə malikdir. Lakin praktikada elə məsələlərə rast gəlirik ki, bu sürət bizi qane etmir. Məsələn, O-dan 9-a kimi ədədlərin bütün ardıcıllığını əks etdirən n uzunluqlu bütün variantlar üçün ən azı 10” addım tələb olunur. Fərz edək ki, hər bir ardıcıllığı təhlil etmək üçün milyonda bir saniyə vaxt tələb olunur. Onda, rəqəmlərinin sayı 5 olan ədəd üçün - onda bir saniyə, 10 olan ədəd üçün - artıq 2 saat 40 dəqiqə. 1 I üçün - bir sutkadan çox, 12 üçün - 10 sutkaya qədər, 13 üçün, demək olar ki, - 4 ay, 14 üçün - 3 ildən çox, 15 üçün isə 30 ildən artıq vaxt tələb olunar. İlk baxışdan bu sanki problem yaratmır, axı indiki kompüterlərin sürəti çox böyükdür! Lakin, baxsaq görərik ki, 1998-ci ildən 2003-cü ilə qədər fərdi kompüterlərin sürəti təxminən 10 dəfə artmışdır. Belə nəticəyə gələ bilərik ki, hər 5 ildən bir kompüterlərin sürəti 10 dəfə artacaqdır. Və. əgər biz bu gün n uzunluqlu məsələni həll edə biliriksə, deməli, 1 üçün bu məsələni yalnız 5 ildən sonra həll edə biləcəyik. Baxdığımız konkret misal üçün biz n^ll halı üçün bu gün bu məsələni həll edə biliriksə, onda yalnız 20 ildən sonra n = 15 halı üçün həmin məsələni həll edə biləcəyik. n=20 halı üçün məsələni həll etmək istəyən proqramçının halına isə acımaqdan başqa bir şey qalmır.