Müvafiq alqoritmə uyğun olaraq proqramın vaxt səmərəliliyi. Alqoritmlərin və verilənlər strukturlarının mürəkkəbliyi və səmərəliliyi anlayışları. Alınan materialla nə edəcəyik?

Alqoritm səmərəliliyi alqoritmin istifadə etdiyi hesablama resursları ilə əlaqəli olan alqoritmin xassəsidir. Alqoritmin tələb etdiyi resursları müəyyən etmək üçün alqoritm təhlil edilməlidir. Alqoritm səmərəliliyi təkrarlanan və ya davamlı proseslərin istehsal məhsuldarlığına oxşar hesab edilə bilər.

Maksimum səmərəliliyə nail olmaq üçün biz resurs istifadəsini azaltmaq istəyirik. Bununla belə, müxtəlif resursları (vaxt və yaddaş kimi) birbaşa müqayisə etmək mümkün deyil, ona görə də iki alqoritmdən hansının daha səmərəli hesab ediləcəyi çox vaxt hansı amilin daha vacib olmasından asılıdır, məsələn, yüksək sürət tələbi, minimum yaddaş istifadəsi və ya başqa bir ölçü. səmərəlilik.

Nəzərə alın ki, bu məqalə YOX Proqramın optimallaşdırılması, kompilyatorun optimallaşdırılması məqalələrində müzakirə olunan alqoritmin optimallaşdırılması haqqında, dövrünün optimallaşdırılması, obyekt kodu optimallaşdırıcısı, və s. "Optimallaşdırma" termininin özü yanlışdır, çünki edilə bilən hər şey "təkmilləşdirmə" çətiri altına düşür.

Fon

İcra müddətinə vurğu ilə səmərəliliyin əhəmiyyəti 1843-cü ildə Ada Lovelace tərəfindən Charles Babbage-nin mexaniki analitik mühərriki ilə bağlı vurğulanmışdır:

“Demək olar ki, bütün hesablamalarda prosesi uğurla başa çatdırmaq üçün çoxlu konfiqurasiya seçimi mümkündür və müxtəlif konvensiyalar hesablamanın aparılması üçün seçimə təsir etməlidir. Əsas odur ki, hesablamanı yerinə yetirmək üçün tələb olunan vaxtı minimuma endirəcək konfiqurasiya seçməkdir."

Erkən elektron kompüterlər həm sürət, həm də yaddaş baxımından çox məhdud idi. Bəzi hallarda, bir tapşırıq yüksək sürətə nail olmaq üçün ya böyük həcmdə yaddaşdan istifadə etməli, ya da az miqdarda iş yaddaşından istifadə edən daha yavaş bir alqoritmdən istifadə etməli olduğu zaman-yaddaş mübadiləsinin olduğu dərk edilmişdir. Bu halda, mövcud yaddaşın kifayət etdiyi ən sürətli alqoritmdən istifadə edilmişdir.

Müasir kompüterlər o ilk kompüterlərdən qat-qat sürətlidir və daha çox yaddaşa malikdir (kiqabayt əvəzinə gigabayt). Bununla belə, Donald Knuth səmərəliliyin mühüm amil olaraq qaldığını vurğulayır:

"Müəyyən edilmiş mühəndislik fənlərində 12% inkişaf asanlıqla əldə edilə bilər və heç vaxt qadağanedici sayılmayıb və mən hesab edirəm ki, proqramlaşdırmada da eyni şey olmalıdır."

Baxış-icmal

Alqoritm, onun resurs istehlakı (və ya resurs dəyəri) hansısa məqbul səviyyədə və ya ondan aşağı olarsa, səmərəli hesab edilir. Kobud desək, burada "məqbul" "alqoritm mövcud kompüterdə ağlabatan müddət ərzində işləyəcək" deməkdir. Çünki 1950-ci illərdən etibarən kompüterlərin emal gücündə və mövcud yaddaşında nəzərəçarpacaq artım müşahidə olunduğundan, indiki “məqbul səviyyə” hətta 10 il bundan əvvəl də məqbul deyildi.

Kompüter istehsalçıları vaxtaşırı yeni, çox vaxt daha güclü modellər buraxırlar. Proqram təminatının qiyməti kifayət qədər yüksək ola bilər, ona görə də bəzi hallarda mövcud kompüterinizə uyğun olan daha sürətli kompüter almaqla daha yaxşı performans əldə etmək daha asan və daha ucuzdur.

Alqoritmin istifadə etdiyi resursları ölçməyin bir çox yolu var. Ən çox istifadə edilən iki ölçü istifadə olunan sürət və yaddaşdır. Digər ölçülərə ötürmə sürəti, müvəqqəti disk istifadəsi, uzunmüddətli disk istifadəsi, enerji istehlakı, ümumi sahiblik dəyəri, xarici siqnallara cavab müddəti və s. daxil ola bilər. Bu ölçmələrin çoxu alqoritmin giriş məlumatlarının ölçüsündən (yəni məlumatların işlənməsini tələb edən kəmiyyətlərdən) asılıdır. Ölçmələr həmçinin məlumatların təqdim edilmə üsulundan asılı ola bilər (məsələn, bəzi çeşidləmə alqoritmləri artıq çeşidlənmiş məlumatlarda və ya verilənlər tərs qaydada çeşidləndikdə zəif işləyir).

Təcrübədə tələb olunan dəqiqlik və/yaxud etibarlılıq kimi alqoritmin effektivliyinə təsir edən digər amillər də mövcuddur. Aşağıda izah edildiyi kimi, alqoritmin həyata keçirilmə üsulu da real performansa əhəmiyyətli təsir göstərə bilər, baxmayaraq ki, həyata keçirilməsinin bir çox aspektləri optimallaşdırma məsələləridir.

Nəzəri təhlil

Alqoritmlərin nəzəri təhlilində alqoritmin mürəkkəbliyini onun asimptotik davranışında qiymətləndirmək, yəni girişin ölçüsündən asılı olaraq alqoritmin mürəkkəbliyini əks etdirmək adi təcrübədir. n Böyük O qeydindən istifadə olunur. Bu qiymətləndirmə ümumiyyətlə böyüklər üçün olduqca dəqiqdir n, lakin kiçik dəyərlərdə yanlış nəticələrə səbəb ola bilər n(Beləliklə, yavaş hesab edilən qabarcıq çeşidləmə, yalnız bir neçə elementi çeşidləmək lazımdırsa, sürətli çeşidləmədən daha sürətli ola bilər).

Təyinat	ad	Nümunələr
O(1) (\displaystyle O(1)\,)	daimi	Ədədin cüt və ya tək olduğunu müəyyən etmək. Sabit ölçülü axtarış cədvəlindən istifadə. Element seçmək üçün uyğun hash funksiyasından istifadə edin.
O (log ⁡ n) (\displaystyle O(\log n)\,)	loqarifmik	Binar axtarış və ya balanslaşdırılmış ağacdan istifadə edərək çeşidlənmiş massivdə elementin tapılması, binomial yığındakı əməliyyatlara bənzər.
O(n) (\displaystyle O(n)\,)	xətti	Sıralanmamış siyahıda və ya balanssız ağacda elementin tapılması (ən pis vəziyyət). İki əlavə n uç-to-end daşıma istifadə -bit nömrələri.
O (n log ⁡ n) (\displaystyle O(n\log n)\,)	kvazilinear, loqarifmik xətti	Sürətli Furye çevrilməsi, yığın çeşidləmə, sürətli çeşidləmə (ən yaxşı və orta hal), birləşmə çeşidini hesablayın
O (n 2) (\displaystyle O(n^(2))\,)	kvadrat	İkini vurmaq n-sadə bir alqoritmdən istifadə edən rəqəmli nömrələr, qabarcıq çeşidləmə (ən pis hal), qabıq çeşidləmə, sürətli çeşidləmə (ən pis vəziyyət), seçim çeşidi, daxiletmə çeşidi
O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1)	eksponensial	Dinamik proqramlaşdırmadan istifadə edərək səyahət edən satıcı probleminin (dəqiq) həllinin tapılması. Tam axtarışdan istifadə edərək iki məntiqi ifadənin ekvivalent olub olmadığını müəyyən etmək

Doğrulama Testləri: Performansın ölçülməsi

Proqram təminatının yeni versiyaları üçün və ya rəqib sistemlərlə müqayisəni təmin etmək üçün bəzən alqoritmlərin nisbi performansını müqayisə etmək üçün etalonlardan istifadə olunur. Məsələn, yeni çeşidləmə alqoritmi buraxılarsa, o, sələfləri ilə müqayisə oluna bilər ki, alqoritm ən azı digərləri kimi məlum məlumatlarda səmərəli olsun. Performans testləri istifadəçilər tərəfindən müxtəlif istehsalçıların məhsullarını müqayisə etmək üçün hansı məhsulun funksionallıq və performans baxımından onların tələblərinə ən uyğun olacağını qiymətləndirmək üçün istifadə edilə bilər.

Bəzi etalon testlər müxtəlif tərtib və tərcümə dillərinin müqayisəli təhlilini təmin edir, məsələn Roy Longbottomun PC Benchmark Collection və Kompüter Dili Testləri Oyunu bəzi proqramlaşdırma dillərində tipik tapşırıqların icrasının performansını müqayisə edir.

İcra məsələləri

İcra məsələləri də faktiki fəaliyyətə təsir göstərə bilər. Buraya proqramlaşdırma dilinin seçimi və alqoritmin əslində kodlaşdırılma üsulu, seçilmiş dil üçün tərcüməçi seçimi və ya istifadə edilən tərtibçi seçimləri və hətta istifadə olunan əməliyyat sistemi daxildir. Bəzi hallarda tərcüməçi kimi həyata keçirilən dil kompilyator kimi həyata keçirilən dildən xeyli yavaş ola bilər.

Proqramçının nəzarətindən kənar vaxta və ya yaddaşın istifadəsinə təsir edə biləcək digər amillər də var. Buraya məlumatların uyğunlaşdırılması, detallaşdırma, zibil toplama , təlimat səviyyəsində paralellik və alt proqram çağırışı .

Bəzi prosessorlar vektor əməliyyatlarını yerinə yetirmək qabiliyyətinə malikdirlər ki, bu da bir əməliyyatın bir neçə operandın işləməsinə imkan verir. Bu cür xüsusiyyətləri proqramlaşdırma və ya tərtib səviyyəsində istifadə etmək asan və ya asan olmaya bilər. Ardıcıl hesablamalar üçün nəzərdə tutulmuş alqoritmlər paralel hesablamaları yerləşdirmək üçün tam yenidən dizayn tələb edə bilər.

Prosessor uyğunluğu ilə bağlı başqa bir problem yarana bilər, burada təlimatlar fərqli şəkildə həyata keçirilə bilər, belə ki, bəzi modellərdəki təlimatlar digər modellərdə nisbətən yavaş ola bilər. Bu, optimallaşdıran kompilyator üçün problem ola bilər.

Resurs istifadəsinin ölçülməsi

Ölçmələr adətən girişin ölçüsündən asılı olaraq ifadə edilir n.

Ən vacib iki ölçü bunlardır:

Vaxt: Alqoritmin CPU-ya nə qədər vaxt sərf etməsi.
Yaddaş: Alqoritm üçün nə qədər iş yaddaşı (adətən RAM) lazımdır. Bunun iki aspekti var: kod üçün yaddaşın miqdarı və kodun işlədiyi məlumat üçün yaddaşın miqdarı.

Batareya ilə işləyən kompüterlər (məsələn, noutbuklar) və ya çox uzun/böyük hesablamalar (məsələn, superkompüterlər) üçün fərqli bir ölçmə növü maraq doğurur:

Birbaşa enerji istehlakı: Kompüteri idarə etmək üçün tələb olunan enerji.
Dolayı enerji istehlakı: Soyutma, işıqlandırma və s. üçün tələb olunan enerji.

Bəzi hallarda, digər, daha az ümumi ölçmələrə ehtiyac var:

Ötürücü ölçüsü: Bant genişliyi məhdudlaşdırıcı amil ola bilər. Sıxılma, ötürülən məlumatların miqdarını azaltmaq üçün istifadə edilə bilər. Qrafik və ya şəklin (məsələn, Google loqosu) göstərilməsi on minlərlə baytın ötürülməsi ilə nəticələnə bilər (bu halda 48K). Bunu "Google" sözündə altı baytın ötürülməsi ilə müqayisə edin.
Xarici yaddaş: Diskdə və ya digər xarici yaddaş cihazında tələb olunan yaddaş. Bu yaddaş müvəqqəti saxlama və ya gələcək istifadə üçün istifadə edilə bilər.
Cavab vaxtı: Bu parametr kompüterin xarici hadisələrə tez cavab verməli olduğu real vaxt proqramları üçün xüsusilə vacibdir.
Ümumi Mülkiyyət Dəyəri: Parametr bir alqoritmin icrası üçün nəzərdə tutulduqda vacibdir.

Vaxt

Nəzəriyyə

Bu test növü proqramlaşdırma dilinin, kompilyatorun və onun variantlarının seçimindən də əhəmiyyətli dərəcədə asılıdır, belə ki, müqayisəli alqoritmlər eyni şəraitdə həyata keçirilməlidir.

Yaddaş

Bu bölmə alqoritmin ehtiyac duyduğu əsas yaddaşın (çox vaxt RAM) istifadəsindən bəhs edir. Yuxarıdakı vaxt təhlilində olduğu kimi, alqoritmin təhlili adətən istifadə edir alqoritmin məkan mürəkkəbliyi tələb olunan iş vaxtı yaddaşını giriş ölçüsündən asılı olaraq qiymətləndirmək. Nəticə adətən "O" böyük ifadəsi ilə ifadə edilir.

Yaddaşdan istifadənin dörd aspekti var:

Alqoritm kodunu saxlamaq üçün tələb olunan yaddaş miqdarı.
Giriş məlumatları üçün tələb olunan yaddaş miqdarı.
İstənilən çıxış üçün tələb olunan yaddaş miqdarı (bəzi alqoritmlər, məsələn, növlər, girişi tez-tez yenidən təşkil edir və çıxış üçün əlavə yaddaş tələb etmir).
Hesablama zamanı hesablama prosesi üçün tələb olunan yaddaşın miqdarı (buraya adlandırılmış dəyişənlər və rekursiyadan istifadə edərkən əhəmiyyətli ola bilən alt proqram çağırışları üçün tələb olunan istənilən yığın sahəsi daxildir).

Erkən elektron kompüterlər və ev kompüterləri nisbətən kiçik iş yaddaşına malik idi. Beləliklə, 1949-cu ildə EDSAC-ın maksimum iş yaddaşı 1024 17 bitlik söz idi və 1980-ci ildə Sinclair ZX80 1024 bayt iş yaddaşı ilə buraxıldı.

Müasir kompüterlər nisbətən böyük həcmdə yaddaşa (bəlkə də gigabayt) malik ola bilər, ona görə də alqoritm tərəfindən istifadə olunan yaddaşın müəyyən yaddaş həcminə sıxılması əvvəlkindən daha az tələb olunur. Bununla belə, üç fərqli yaddaş kateqoriyasının mövcudluğu əhəmiyyətlidir:

Keş (tez-tez statik RAM) - CPU ilə müqayisə edilə bilən sürətlə işləyir
Əsas fiziki yaddaş (tez-tez dinamik RAM) - CPU-dan bir qədər yavaş işləyir
Virtual yaddaş (tez-tez diskdə) - böyük yaddaş illüziyasını verir, lakin RAM-dən minlərlə dəfə yavaş işləyir.

Tələb olunan yaddaşı kompüterin ön yaddaşına sığdıran alqoritm əsas yaddaşa uyğun gələn alqoritmdən qat-qat sürətlidir ki, bu da öz növbəsində virtual məkandan istifadə edən alqoritmdən xeyli sürətli olacaq. Məsələləri çətinləşdirən odur ki, bəzi sistemlərdə üç səviyyəyə qədər keş yaddaşı var. Fərqli sistemlərdə bu tip yaddaşın müxtəlif həcmləri var, ona görə də alqoritmdə yaddaş effekti bir sistemdən digərinə əhəmiyyətli dərəcədə dəyişə bilər.

Elektron hesablamanın ilk dövrlərində alqoritm və onun məlumatları əsas yaddaşa uyğun gəlmirsə, ondan istifadə etmək mümkün deyildi. Bu günlərdə virtual yaddaşdan istifadə böyük yaddaş təmin edir, lakin performans bahasına. Alqoritm və onun məlumatları keş yaddaşa sığarsa, çox yüksək sürətə nail olmaq olar, buna görə də tələb olunan yaddaşı minimuma endirmək vaxtı minimuma endirməyə kömək edir. Tamamilə önbelleğe uyğun olmayan, lakin təmin edən bir alqoritm bağlantıların lokalizasiyası, nisbətən tez işləyə bilər.

Effektiv alqoritmlərin nümunələri

Proqramlaşdırmanın hazırkı vəziyyətinin tənqidi

Proqramlar kompüterlərin daha sürətli olmasından daha sürətlə yavaşlayır.

May bildirir:

Geniş yayılmış sistemlərdə təlimatın icrasını yarıya endirmək batareyanın ömrünü iki dəfə artıra bilər və böyük verilənlər daha yaxşı alqoritmlər üçün imkan yaradır: N x N-dən N x log(N)-ə qədər əməliyyatların sayının azaldılması böyük N... üçün güclü təsir göstərir. =30 milyard, bu dəyişikliklər 50 illik texnoloji təkmilləşdirmələrə bənzəyir.

Ən yaxşı alqoritm üçün müsabiqə

Aşağıdakı müsabiqələr keyfiyyət meyarları hakimlər tərəfindən müəyyən edilən ən yaxşı alqoritmlərin işlənib hazırlanmasında iştiraka dəvət edir:

həmçinin bax

Arifmetik kodlaşdırma entropiya kodlaşdırmasının bir növüdür dəyişən kod uzunluğu ilə məlumatların səmərəli sıxılması üçün
Assosiativ massiv istifadə edildikdə daha səmərəli edilə bilən məlumat strukturudur ağaclar PATRICIA və ya Judy serialları
Performans testi - müəyyən hallarda müqayisəli icra müddətini ölçmək üsulu
Ən yaxşı, ən pis və orta hal- üç ssenari üzrə icra müddətini qiymətləndirmək üçün konvensiyalar
İkili axtarış sıralanmış siyahıları axtarmaq üçün sadə və effektiv üsuldur
Filial masası

Mühazirənin məqsəd və vəzifələri: alqoritmlərin və məlumat strukturlarının mürəkkəbliyi və səmərəliliyinin təhlili üsullarına giriş.

Əsas məsələlər: alqoritmlərin effektivliyinin eksperimental və analitik təhlili.

N. Wirth-in klassik ifadəsi "Yaxşı proqram yaxşı düşünülmüş alqoritm və effektiv məlumat strukturlarının vəhdətidir."

Alqoritm Analizi
"Alqoritm və məlumat strukturları" anlayışları kompüter texnologiyası sahəsində mərkəzi yer tutur, lakin müəyyən məlumat strukturlarını və alqoritmləri "yüksək keyfiyyətli və səmərəli" adlandırmaq üçün onların təhlili üçün dəqiq üsullardan istifadə edilməlidir. Təbii keyfiyyət meyarı kimi, ilk növbədə, icra vaxtını vurğulamaq təbiidir. Həmçinin sərf olunan yaddaş və disk sahəsi resurslarının miqdarı, verilənlərə çıxış sürəti (məlumat strukturunun səmərəliliyi) vacibdir. Qərarların etibarlılığına və etibarlılığına, onların sabitliyinə də diqqət yetirilməlidir.

Alqoritm konkret icraya bağlanmamalıdır. İstifadə olunan proqramlaşdırma alətlərinin müxtəlifliyinə görə həyata keçirilməsində fərqli olan alqoritmlər səmərəliliyi ilə fərqlənən nəticələr verə bilər.

Məlumat strukturunda alqoritmin və ya əməliyyatın icra müddəti, bir qayda olaraq, bir sıra amillərdən asılıdır. Alqoritmin icrası üçün tələb olunan vaxtı təyin etməyin ən sadə yolu alqoritmin işləməsindən əvvəl və sonrakı vaxtı ölçməkdir.

Bununla belə, yadda saxlamaq lazımdır ki, vaxtın hesablanmasının bu metodu dəqiq deyil, ilk növbədə, başa düşülməlidir ki, müasir əməliyyat sistemlərində bir neçə tapşırıq paralel olaraq yerinə yetirilə bilər və test işinin icrası digər növlərlə birləşdirilə bilər. fəaliyyətinin. Bundan əlavə, başa düşülməlidir ki, sabit bir asılılığa yalnız təkrar sınaqlar aparmaqla nail olmaq olar, əks halda ilkin məlumatların xüsusiyyətlərindən və digər amillərdən asılı olaraq təsadüfi amillərin işinin son nəticəsinə təsir göstərməsi səbəbindən. alqoritmin vaxtı da təsadüfi dəyişən olacaq. Tədqiqat apararkən alqoritmi fərqli ilkin məlumat dəsti ilə idarə etmək lazımdır, adətən verilənlərin özü təsadüfi yaradılır, buna görə də müxtəlif məlumat dəstlərinə görə sərf olunan vaxt da fərqli olacaq.

Bir sıra təxminlər əldə edildikdən sonra qrafiki qurmaq və təxmini hesablamaq olar.

Qeyri-trivial alqoritmlərdən istifadə edərkən belə bir təhlil həmişə istifadə edilməlidir; bu, bir neçə onlarla qeyd və ya elementdən ibarət sınaq dəstini deyil, tam həcmdə real məlumatların düzəldilməsi üçün istifadə edərək, bir proqram hazırlamaq tövsiyəsinə bənzəyir, bu da dəyişiklikdən və ya hətta dəyişdirilmədən qaçır. alqoritm və ya struktur məlumatlarının sonradan qeyri-mümkün olduğu sübut olunarsa, onların tam yenidən işlənməsi. Eksperimental nəticələr toplusuna sahib olmaqla siz interpolyasiya və ekstrapolyasiya həyata keçirə və real şəraitdə alqoritmin davranışını təyin edə bilərsiniz.

Ümumiyyətlə, deyə bilərik ki, alqoritm və ya verilənlər strukturu metodunun icra müddəti mənbə verilənlərin ölçüsü artdıqca artır, baxmayaraq ki, ölçüsü bərabər olsa belə, bu, həm də verilənlərin növündən asılıdır. Bundan əlavə, icra müddəti icra, kompilyasiya və kompilyasiyanın həyata keçirildiyi aparatdan (prosessor, takt tezliyi, yaddaş ölçüsü, disk sahəsi və s.) və proqram təminatından (əməliyyat mühiti, proqramlaşdırma dili, kompilyator, tərcüməçi və s.) asılıdır. alqoritmin icrası. Məsələn, bütün digər şeylər bərabər olduqda, müəyyən miqdarda mənbə məlumatı üçün alqoritmin icra müddəti, daha güclü kompüterdən istifadə edərkən və ya alqoritmi proqram kimi maşın kodunda yazarkən virtual maşın tərəfindən icrası ilə müqayisədə daha az olacaq. bayt kodlarına çevrilməsi.

Nəticə ondan ibarətdir ki, alqoritmlərin empirik təhlilinin aparılması həqiqətən etibarlı deyil. Əsas çatışmazlıqlar aşağıdakı üç nöqtəyə endirilə bilər:

1) təcrübələr yalnız ilkin məlumatların məhdud dəstindən istifadə etməklə həyata keçirilə bilər; başqa dəstdən istifadə etməklə əldə edilən nəticələr nəzərə alınmır.

2) iki alqoritmin effektivliyini müqayisə etmək üçün onların icra müddətini müəyyən etmək üçün təcrübələrin eyni aparat və proqram təminatı üzərində aparılması zəruridir;
3) alqoritmin icra müddətini eksperimental olaraq öyrənmək üçün onun icrasını və icrasını həyata keçirmək lazımdır.

Beləliklə, alqoritmləri təhlil etmək üçün ümumi analiz metodlarından istifadə etmək zərurətinə gəldik ki, bu da imkan verir:

1) müxtəlif növ daxilolma məlumatlarını nəzərə alır;

2) aparat və proqram təminatından asılı olmayaraq istənilən iki alqoritmin nisbi effektivliyini qiymətləndirməyə imkan verir;

3) alqoritmin təsvirinə əsasən onun bilavasitə icrası və ya təcrübələri olmadan həyata keçirilə bilər.

Ümumi təhlilin mahiyyəti ondan ibarətdir ki, f=f(n1, .., nm) funksiyası müəyyən alqoritmə aid edilir. Ən sadə formada, bu, bir dəyişən n1-in funksiyasıdır - giriş məlumatlarının miqdarı. Bununla belə, başqa dəyişənlər də ola bilər - məsələn, hesablamanın dəqiqliyi və ya onun etibarlılığı. Belə ki, böyük ədədlər (ikili təsvirin uzunluğu 200 bitdən çox) zamanı müəyyən ədədin sadə olub-olmadığını müəyyən etmək üçün etibarlılığı dəyişə bilən ehtimal metodundan istifadə edilir. Ən məşhur funksiyalar xətti, güc və loqarifmik funksiyalardır. Buna görə də, onlarla işləməyin əsaslarını xatırlamağa vaxt ayırmalısınız.

Alqoritmlər qurarkən birinci mərhələ proqramlaşdırma dilindən deyil, insan dilində təsvirdən istifadə etməklə baş verir. Bu cür təsvirlər proqram deyil, eyni zamanda adi mətndən daha strukturlaşdırılmışdır. Xüsusilə, “yüksək səviyyəli” təsvirlər təbii dil və ümumi proqramlaşdırma dili strukturlarını birləşdirərək onları əlçatan, lakin məlumatlandırıcı edir. Bu cür təsvirlər məlumat strukturunun və ya alqoritmin yüksək səviyyəli təhlilini asanlaşdırır. Belə təsvirlər adətən psevdokod adlanır. Onu da qeyd etmək lazımdır ki, psevdokod çox vaxt analiz üçün konkret proqramlaşdırma dilindəki koddan daha faydalıdır.

Bəzən müəyyən məlumat strukturu və ya alqoritmlə bağlı müəyyən ifadələri sübut etməyə ehtiyac yaranır. Məsələn, alqoritmin düzgünlüyünü və icra sürətini nümayiş etdirməlisiniz. İfadələri ciddi şəkildə sübut etmək üçün ifadələrin sübutu və ya əsaslandırılması kimi xidmət edəcək riyazi dildən istifadə etmək lazımdır. Bunu sübut etməyin bir neçə sadə yolu var.

Bəzən ifadələr ümumiləşdirilmiş formada yazılır: “s çoxluğunda v xassəsinə malik x elementi var. Bu ifadəni sübut etmək üçün bu xüsusiyyətə malik olan s-ə x “aid” misalını vermək kifayətdir. Belə bir ümumiləşdirilmiş formada, bir qayda olaraq, mümkün olmayan ifadələr yazılır, məsələn: "s dəstinin hər bir x elementi P xüsusiyyətinə malikdir." Bu ifadənin yanlışlığını sübut etmək üçün sadəcə olaraq bir misal göstərmək kifayətdir: x P xassəsinə malik olmayan s-ə “aiddir”. Bu halda x elementi əks-nümunə kimi çıxış edəcəkdir.

Misal: Bildirilir ki, n 1-dən böyük tam ədəddirsə, 2^n - 1 formasının istənilən ədədi sadədir. Bəyanat yanlışdır.

Sübut: Kiminsə səhv etdiyini sübut etmək üçün əks nümunə tapmaq lazımdır.

Bu əks nümunədir: 2^4 - 1 = 15, 15= 3 * 5.

Ziddiyyətlə sübuta əsaslanan başqa bir yol var (inkardan istifadə etməklə). Bu vəziyyətdə əsas üsullar ziddiyyət və ziddiyyətdir. Kontrast üsullarından istifadə güzgüləşdirməyə bənzəyir: “x doğrudursa, onda y doğrudur” olduğunu sübut etmək üçün biz bunun əksini irəli sürəcəyik, “y yanlışdırsa, x yanlışdır”. Məntiqi nöqteyi-nəzərdən bu ifadələr eynidir, lakin birincinin kotropoziyası olan ikinci ifadə daha əlverişlidir.

Misal:Əgər a*b tək ədəddirsə, a tək və ya b təkdir.

Sübut: bu müddəayı sübut etmək üçün ziddiyyəti nəzərdən keçirin: “Əgər a cüt ədəddirsə və b təkdirsə, a*b cütdür. Bəzi x tam ədədi üçün a = 2*x olsun. Onda a*b = 2*i*b və buna görə də a*b hasilatı cütdür.

Ziddiyyətlə sübut üsullarından istifadə edərkən məntiqdən istifadə etmək faydalıdır.

A və ya b = a və ya b-nin yerinə yetirilməsini tələb edir və ya hər iki a və b eyni vaxtda.
. a və b = a və b-nin eyni vaxtda yerinə yetirilməsini tələb edir.
. a xor b = a yerinə yetirilməsini tələb edir, lakin b deyil, və ya b, lakin a deyil.

q müddəasının doğru olduğunu sübut etmək üçün ziddiyyət metodundan istifadə edərkən əvvəlcə q-nin yalan olduğunu qəbul edir və sonra belə bir fərziyyənin ziddiyyətə səbəb olduğunu göstərir (məsələn, 2 * 2).<>4). Belə bir ziddiyyətə gələrək, q-nin yanlış olduğu bir vəziyyətin mövcud olmadığını və buna görə də q-nin doğru olduğunu iddia edə bilərik.

Əksər hallarda proqramın icra müddəti və ya məkandan istifadə haqqında ifadələr tam ədəd n parametrindən istifadə edir (problemin “ölçüsü”nü təmsil edir). Sonra x(n) ifadəsini tərtib etdikdə, bir sıra qiymətlər üçün n belə ifadələr ekvivalentdir. Bu müddəa “sonsuz” ədədlər toplusuna aid olduğu üçün, hərtərəfli birbaşa sübut təqdim etmək mümkün deyil. Belə hallarda induksiya üsullarından istifadə olunur. İnduksiya üsulu fakta əsaslanır; ki, hər hansı n > 1 üçün. Doğru olduğu bilinən bir şeylə başlayan və son nəticədə q(n)-nin doğru olduğunu sübut edən sonlu hərəkətlər ardıcıllığı var. Beləliklə, induksiya ilə sübut n=1,2,3 və s. üçün q(n)-nin doğru olması ifadəsi ilə başlayır. bir qədər sabit k. Sonra sübut edirik ki, q(n+1), q(n+2) induksiyalarının növbəti “addımı” n > k üçün də doğrudur.

Alqoritmləri təhlil edərkən, əməliyyatların sayını və onların yerinə yetirilmə vaxtını hesablayarkən "xırda detalları" nəzərə almamalı, sabit amilləri və sabitləri nəzərə almamalısınız. Təcrübədə böyük funksiya anlayışından istifadə olunur HAQQINDA. tutaq ki, iki f(n) və g(n) funksiyası var, fərz edilir ki, f(n)<= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

Məsələn, massivdə sıfıra bərabər olan elementlərin sayının hesablanması alqoritmi O(n) ilə təsvir olunur, burada n elementlərin sayıdır.

1) 20n3+7.2n2-21.78n + 5 O(n3) kimi təsvir edilir.

2)xn-2 + a(0) O(xn) kimi təsvir edilir.

2) 3*log(n) + log(log(n)) O(log(n)) kimi təsvir olunur.

3) 2100 O(1) kimi təsvir edilir

4) 5/n O(1/n) kimi təsvir edilir.

Nəzərə alın ki, o(n) funksiyası yuxarıdan hədəf vaxt xərcləri funksiyasını məhdudlaşdırır, lakin siz həmişə O(n) funksiyasını seçməyə çalışmalısınız ki, maksimum dəqiqlik olsun.

Artan qaydada ən məşhur O funksiyaları:

Asimptotik analizdən istifadə edərkən diqqətli olun ki, O qeydindən istifadə edərkən çox vaxt sabit amilləri və əlavə sabitlərini laqeyd edirsiniz. Lakin bu qiymət kifayət qədər böyükdürsə, O(1) funksiyasının forması O(n) funksiyasının təsvir etdiyi alqoritmdən daha üstün olsa da, təbii ki, praktiki tətbiq qazanacaq ikinci alqoritmdir.

f(n) funksiyasının növündən asılı olaraq alqoritmlərin aşağıdakı mürəkkəblik sinifləri fərqləndirilir.

Mürəkkəblik funksiyasından asılı olaraq alqoritm mürəkkəblik sinifləri
Baxın f(n)	Alqoritmlər sinfinin xüsusiyyətləri
	Əksər funksiyalar üçün təlimatların əksəriyyəti bir və ya bir neçə dəfə yerinə yetirilir. Əgər proqramdakı bütün göstərişlər bu xüsusiyyətə malikdirsə, o zaman proqramın icra müddəti sabitdir.
log N	Proqramın icra müddəti loqarifmik olduqda, N artdıqca proqram daha yavaş olur.Belə icra müddətləri adətən böyük problemi kiçik alt problemlər toplusuna endirən, hər addımda problemin ölçüsünü müəyyən sabit faktorla azaldan proqramlarla əlaqələndirilir. Bazanın dəyişdirilməsi loqarifmin qiymətinin dəyişməsinə çox təsir etmir: n
N	Proqramın icra müddəti xətti olduqda, bu, adətən hər bir giriş elementinin az emaldan keçməsi deməkdir.
N log N	N log N ilə mütənasib icra vaxtı alqoritm problemi daha kiçik alt problemlərə bölmək, onları müstəqil həll etmək və sonra həlləri birləşdirməklə həll etdikdə baş verir.
N 2	Alqoritmin işləmə müddəti kvadratik olduqda, nisbətən kiçik məsələlərin həllində praktik istifadə üçün faydalıdır. Kvadrat icra müddəti adətən bütün cüt məlumat elementlərini emal edən alqoritmlərdə (bəlkə də ikiqat yuva dövrəsində) görünür.
N 3	Üçlü məlumat elementlərini emal edən oxşar alqoritm (bəlkə də üçlü yuvalanma dövrəsində) kub icra müddətinə malikdir və praktiki olaraq yalnız kiçik problemlər üçün tətbiq olunur.
2 N	Yalnız eksponensial işləmə vaxtı olan bir neçə alqoritm praktik tətbiqlərə malikdir, baxmayaraq ki, belə alqoritmlər kobud güc kimi bir problemi birbaşa həll etməyə cəhd edərkən təbii olaraq yaranır.

Sonsuzluqda mürəkkəbliyin asimptotik funksiyalarını öyrənmək üçün riyazi metodlara əsaslanaraq, alqoritmlərin beş sinfi müəyyən edilmişdir.

1. Sabit icra müddəti olan sürətli alqoritmlər sinfi, onların mürəkkəblik funksiyası O(1). Aralıq vəziyyəti mürəkkəbliyi O(log N) olan alqoritmlər tutur, onlar da bu sinifdə təsnif edilir.

2. Mürəkkəblik funksiyası giriş parametrlərindən çoxhədli təyin olunan rasional və ya çoxhədli alqoritmlər sinfi. Məsələn, O(N), O(N 2, O(N 3).

3. Mürəkkəblik dərəcəsi O(N log N) olan subeksponensial alqoritmlər sinfi.

4.Mürəkkəblik dərəcəsi O(2 N) olan eksponensial alqoritmlər sinfi.

5.Həddindən artıq eksponensial alqoritmlər sinfi. Faktor mürəkkəbliyi olan alqoritmlər var, lakin onların praktiki tətbiqi ümumiyyətlə yoxdur.

Alqoritmin icrası zamanı yaddaş vəziyyəti müəyyən sahələrin ayrılmasını tələb edən dəyərlərlə müəyyən edilir. Bu halda, problemin həlli zamanı əlavə sayda hüceyrələrdən istifadə edilə bilər. D girişi üçün A alqoritmi tərəfindən tələb olunan yaddaş həcmi dedikdə, alqoritmin icrası zamanı istifadə olunan yaddaş xanalarının maksimum sayını nəzərdə tuturuq. Alqoritmin tutum mürəkkəbliyi alqoritmin ən pis halda yaddaş tutumu funksiyasının asimptotik qiymətləndirilməsi kimi müəyyən edilir.

Beləliklə, alqoritmin ən pis, orta və ən yaxşı hallarda resurs mürəkkəbliyi, asimptotik notasiya ilə müəyyən edilmiş və baxılan işə uyğun gələn zaman və tutum mürəkkəbliyi funksiyalarının ardıcıl cüt sinifləri kimi müəyyən edilir.

Prosessual proqramlaşdırmada əsas alqoritmik konstruksiyalar aşağıdakı, budaqlanma və ilmədir. Sabit giriş ölçüsü ilə ən yaxşı, orta və ən pis hallar üçün mürəkkəblik funksiyalarını əldə etmək üçün əsas alqoritmik strukturların qiymətləndirilməsində fərqləri nəzərə almaq lazımdır.

“Aradan” konstruksiyanın mürəkkəbliyi bir-birini izləyən blokların mürəkkəbliyinin cəmidir: f=f 1 +f 2 +...+f n .
"Şalqlama" dizaynının mürəkkəbliyi şərtlə müəyyən edilmiş təlimatların hər birinə keçid ehtimalı ilə müəyyən edilir. Eyni zamanda, vəziyyəti yoxlamaq da müəyyən mürəkkəbliyə malikdir. Ən pis vəziyyətin mürəkkəbliyini hesablamaq üçün ən mürəkkəbliyə malik budaqlanan blok seçilə bilər, ən yaxşı halda daha az mürəkkəb olan blok seçilə bilər. f əgər =f 1 +f onda p sonra +f başqa (1-p sonra)
“Dövrə” konstruksiyanın mürəkkəbliyi dövrənin başa çatması şərtinin (adətən 0(1) qaydasında) və döngənin tamamlanmış təkrarlarının sayının döngə gövdəsinin mümkün olan ən çox əməliyyat sayına hasilinin hesablanması ilə müəyyən edilir. İç-içə döngələr istifadə edilərsə, onların mürəkkəbliyi çoxalır.

Beləliklə, alqoritmin mürəkkəbliyini qiymətləndirmək üçün mürəkkəblik funksiyasını əldə etmək üçün ümumi bir üsul tərtib edilə bilər.

Alqoritmin parçalanması alqoritmdəki əsas strukturların müəyyən edilməsini və mürəkkəbliyin qiymətləndirilməsini nəzərdə tutur. Bu zaman əsas alqoritmik strukturlardan aşağıdakılar nəzərə alınır.
Əsas dil əməliyyatları üçün əmək intensivliyinin sətir-sətir təhlili ya məcmu təhlili (bütün əməliyyatları nəzərə alaraq) və ya əməliyyat təhlilini (hər bir əməliyyatın mürəkkəbliyini nəzərə alaraq) nəzərdə tutur.
Ən yaxşı, orta və ən pis hallar üçün əsas alqoritmik strukturların təhlili metodologiyasına əsaslanan mürəkkəblik funksiyasının tərs tərkibi.

Rekursiv alqoritmlərin resurs səmərəliliyinin qiymətləndirilməsinin bir xüsusiyyəti əlavə yaddaş xərclərini və rekursiyanın təşkili mexanizmini nəzərə almaq ehtiyacıdır. Buna görə də alqoritmlərin rekursiv həyata keçirilməsinin mürəkkəbliyi bir rekursiv çağırış zamanı yerinə yetirilən əməliyyatların sayı, eləcə də belə çağırışların sayı ilə bağlıdır. Dəyərlərin qaytarılması və nəzarətin zəng nöqtəsinə ötürülməsi xərcləri də nəzərə alınır. Tələb olunan stek yaddaşını qiymətləndirərkən nəzərə almaq lazımdır ki, müəyyən bir zamanda bu, stekdə saxlanılan rekursiya fraqmenti deyil, rekursiv çağırışlar zənciridir. Buna görə yığının ölçüsü qəbul edilən paralel rekursiv zənglərin maksimum mümkün sayı ilə müəyyən edilir.

Proqramçı kitabxanası

"Əgər sazlama xətaların aradan qaldırılması prosesidirsə, proqramlaşdırma onları təqdim etmək prosesi olmalıdır"

E. Dijkstra

1.2. Niyə alqoritmləri öyrənin? Alqoritmlərin səmərəliliyi

Birincisi, alqoritmlər kompüter elminin müxtəlif sahələrində hər hansı bir problemin həlli üçün vacib komponentlərdir. Texnologiyanın inkişafının indiki mərhələsində alqoritmlər əsas rol oynayır. Burada belə ümumi vəzifələri xatırlaya bilərsiniz:

müxtəlif mürəkkəblikdə olan riyazi tənliklərin həlli, matrislərin hasilinin, tərs matrislərin tapılması;
malların və insanların daşınmasının optimal yollarının tapılması;
müxtəlif qovşaqlar (istehsalçılar, maşınlar, işçilər, prosessorlar və s.) arasında resursların bölüşdürülməsi üçün optimal variantların tapılması;
genomda uyğun gələn ardıcıllıqların tapılması;
qlobal İnternetdə məlumat axtarmaq;
e-ticarətdə maliyyə qərarlarının qəbulu;
audio və video məlumatların işlənməsi və təhlili.

Bu siyahı davam edir və əslində müəyyən alqoritmlərdən istifadə olunmayan kompüter elmi və informasiya elmi sahəsini tapmaq demək olar ki, mümkün deyil.

İkincisi, yüksək keyfiyyətli və səmərəli alqoritmlər ilk baxışdan kompüter elmlərindən (kvant mexanikası, iqtisadiyyat və maliyyə, təkamül nəzəriyyəsi) uzaq olan sənayelərdə sıçrayışlar üçün katalizator ola bilər.

Üçüncüsü, alqoritmləri öyrənmək həm də bizim riyazi qabiliyyətlərimizi və məntiqi təfəkkürümüzü inkişaf etdirən inanılmaz dərəcədə maraqlı bir prosesdir.

1.3. Alqoritmlərin səmərəliliyi

Fərz edək ki, kompüterin sürəti və yaddaşının həcmi qeyri-müəyyən müddətə artırıla bilər. Onda alqoritmləri öyrənməyə ehtiyac varmı? Bəli, ancaq ayırma metodunun məhdud işləmə müddətinə malik olduğunu və düzgün cavab verdiyini nümayiş etdirmək üçün. Əgər kompüterlər sonsuz sürətli olsaydı, problemi həll etmək üçün ixtiyari düzgün üsul kömək edərdi. Əlbəttə ki, o zaman çox vaxt həyata keçirmək daha asan olan üsul seçilir.

Bu gün kompüterlər çox güclüdür, lakin onların sürəti sonsuz deyil, yaddaş da deyil. Beləliklə, hesablamada tələb olunan yaddaş miqdarı qədər məhdud bir resursdur. Bu resurslardan ağıllı istifadə edilməlidir ki, bu da vaxt və yaddaş resurslarından istifadə baxımından səmərəli olan alqoritmlərin istifadəsi ilə asanlaşdırılır.

Eyni problemi həll etmək üçün nəzərdə tutulmuş alqoritmlər çox vaxt səmərəlilik baxımından çox fərqli ola bilər. Bu fərqlər müxtəlif aparat və proqram təminatının yaratdığı fərqlərdən daha nəzərə çarpan ola bilər.

Yuxarıda qeyd edildiyi kimi, bu bölmə çeşidləmə tapşırığına diqqət yetirəcəkdir. Nəzərə alınacaq birinci alqoritm, inklüziv çeşidləmə, işləmək üçün vaxt tələb edir, onun miqdarı c 1 n 2 olaraq qiymətləndirilir, burada n giriş məlumatının ölçüsüdür (çeşidlənəcək ardıcıllıqdakı elementlərin sayı), c 1 sabitdir. Bu ifadə alqoritmin işləmə müddətinin mənbə məlumatlarının həcmindən necə asılı olduğunu göstərir. Daxiletmə növündə bu asılılıq kvadratdır. İkinci alqoritm, birləşmə çeşidi, vaxt tələb edir, onun miqdarı 2 nLog 2 n olaraq qiymətləndirilir. Tipik olaraq, daxilolma çeşidləmə sabiti birləşmə çeşidləmə sabitindən kiçikdir, yəni n artdıqca c12 ILog 2 n funksiyasından daha sürətli böyüyür. Və bəzi n = n 0 dəyəri üçün sabitlərdəki fərqin təsirinin əhəmiyyətini itirdiyi və gələcəkdə c 2 nLog 2 n funksiyasının hər hansı n > n 0 üçün c 1 n 2-dən az olacağı an çatacaq.

Bunu nümayiş etdirmək üçün iki kompüteri - A və B-ni nəzərdən keçirək. A kompüteri daha sürətlidir və çeşidləmə alqoritmini, B kompüteri isə daha yavaşdır və birləşmə çeşidləmə alqoritmini işlədir. Hər iki kompüter milyon ədəddən ibarət dəsti çeşidləməlidir. Tutaq ki, A kompüteri saniyədə milyard əməliyyat yerinə yetirir, B kompüteri isə cəmi on milyon, A kompüteri B-dən 100 dəfə sürətli işləyir. Fərqi daha nəzərə çarpan etmək üçün deyək ki, aktivləşdirmə metodunun kodu ən yaxşısı tərəfindən yazılıb. prosessorun təlimatlarından istifadə edərək dünyada proqramçı və bu alqoritmlə n ədədi çeşidləmək üçün 2n 2 əməliyyat yerinə yetirmək lazımdır (yəni C 1 = 2). B kompüterində birləşmə çeşidi təcrübəsiz bir proqramçı tərəfindən yüksək səviyyəli bir dildən istifadə edərək yazılmışdır və nəticədə alınan kod 50nlog 2 n əməliyyat tələb edir (yəni c 2 = 50). Beləliklə, bir milyon ədədi çeşidləmək üçün A kompüterinə ehtiyac olacaq

və B kompüterinə -

Buna görə də, işləmə müddəti daha yavaş artan kodun istifadəsi, hətta pis kompüter və pis tərtibçi ilə belə, daha az CPU vaxtı tələb edir! 10.000.000 rəqəmi çeşidləmək üçün birləşmə çeşidləmənin üstünlüyü daha da nəzərə çarpır: daxiletmə çeşidi belə bir tapşırıq üçün təxminən 2,3 gün tələb etdiyi halda, birləşmə çeşidi üçün 20 dəqiqədən az vaxt tələb olunur. Ümumi qayda ondan ibarətdir ki, çeşidlənəcək elementlərin sayı nə qədər çox olarsa, birləşmə çeşidinin üstünlüyü bir o qədər çox olar. Yuxarıdakı misal göstərir ki, kompüter proqramı kimi alqoritmlər də belədir texnologiya. Sistemin ümumi performansı aparatın gücündən olduğu kimi alqoritmin səmərəliliyindən də asılıdır.

Beləliklə, hesablama maşınları üçün ən sadə Turing maşınlarından tutmuş homojen hesablama mühitinə qədər müxtəlif variantlar nəzərdən keçirilir. Onların hamısı alqoritmin mövcud olduğu problemləri həll etmək üçün istifadə edilə bilər. Bu modellər əsasında hesablamanın daha ixtisaslaşmış modelləri qurulur, yəni: budaqlanmayan arifmetik proqramlar, bitli hesablamalar, ikili vektor hesablamaları və qərar ağacları.

Alqoritmlər aşağıdakı xüsusiyyətlərə malikdir:

a) mürəkkəblik;

b) əmək intensivliyi;

c) etibarlılıq və s.

Alqoritmlərin mürəkkəbliyini qiymətləndirmək üçün bir çox meyar var. Çox vaxt maraqlanacağıq böyümə qaydası giriş məlumatlarının miqdarı artdıqca problemi həll etmək üçün tələb olunan vaxt və yaddaş tutumu. Gəlin hər bir konkret tapşırıqla onun adlanan müəyyən bir nömrəni birləşdirək ölçüsü. Məsələn, matrisə vurma məsələsinin ölçüsü faktor matrislərinin ən böyük ölçüsü ola bilər; qrafikdəki problemin ölçüsü verilmiş qrafikin kənarlarının sayı ola bilər və s.

Problemin ölçüsündən asılı olaraq alqoritmin aldığı vaxt deyilir zaman mürəkkəbliyi bu alqoritm. Problem ölçüsü artdıqca bu mürəkkəbliyin həddə davranışı deyilir asimptotik zaman mürəkkəbliyi. Eyni şəkildə müəyyən edilmişdir kapasitiv mürəkkəblik Və asimptotik tutumun mürəkkəbliyi.

Formal hesablama modellərini nəzərdən keçirmək üçün vacib motivasiya hesablama vaxtı üçün aşağı hədlər əldə etmək üçün müxtəlif problemlərin hesablama mürəkkəbliyini aşkar etmək istəyidir. Verilmiş tapşırığı müəyyən vaxtdan az müddətdə yerinə yetirə biləcək heç bir alqoritmin olmadığını göstərmək üçün alqoritmin nə olduğunun dəqiq və bəzən yüksək ixtisaslaşmış tərifi tələb olunur. Belə tərifin bir nümunəsi Turing maşınlarıdır.

4.1.1. Çərçivə və çərçivə maşınları*

İki avtomobili nəzərdən keçirin:

1. Yaddaşa təsadüfi girişi olan maşınlar (bərabər giriş ünvanı maşını - RAM) proqram təlimatlarının özünü dəyişdirə bilmədiyi bir toplayıcı ilə kompüteri modelləşdirir.

2. Saxlanılan proqram modeli yaddaşa təsadüfi giriş və təlimatları dəyişdirmək imkanı olan maşındır (RAM*).

Şəkil 2.9 RAM maşınlarının strukturu (RAM*)

RAM üçün proqram yaddaşa yazılmır, ona görə də proqram özünü dəyişdirmir. Proqram etiketli əmrlər ardıcıllığıdır. Arifmetik təlimatlar, giriş/çıxış təlimatları, dolayı ünvanlama təlimatları və filial təlimatları var. Bütün hesablamalar hər hansı digər yaddaş registrləri kimi ixtiyari tam ədədi saxlaya bilən r 0 (toplayıcı) registrində aparılır. Hər bir əmr iki hissədən ibarətdir - əməliyyat kodu və ünvan. PAM əmrləri Assembly dili əmrlərinin alt çoxluğudur; bu alt çoxluq öz istəyi ilə genişləndirilə bilər, lakin tapşırıqların mürəkkəblik sırası dəyişməyəcək.

Operand aşağıdakı növlərdən biri ola bilər:

1. =i tam ədədin özünü bildirir i və hərfi adlanır;

2. i- məzmunu qeyd edin i (i mənfi olmamalıdır);

3. *i dolayı ünvanlama deməkdir, yəni operandın qiyməti reyestrin məzmunudur j,Harada j- reyestrdə olan tam ədəd I;Əgər j<0, maşın dayanır.

Proqramın dəyərini təyin edə bilərsiniz R iki obyektdən istifadə etməklə: qeyri-mənfi tam ədədlər dəstindən tam ədədlər dəstinə c xəritələşdirilməsi və yerinə yetiriləcək növbəti əmri təyin edən “komanda sayğacı”. c funksiyasıdır yaddaş ekranı, yəni c(i)- registr nömrəsində olan tam ədəd I (məzmun qeydiyyatdan keçin I).

Başlanğıcda с(i)=0 hamı üçün i 0 , proqram sayğacı P-də birinci təlimata qoyulur və çıxış lenti boşdur. Edamdan sonra k dan komanda R sayğac avtomatik olaraq keçir (k+1)-th (yəni sonrakı) əmri, əgər k-mənim komandam JUMP, HALT, JGTZ və bu kimi komanda deyildi.

RAM* proqramı yaddaş registrlərində yerləşir. Hər bir RAM* əmri iki ardıcıl yaddaş registrini tutur: birinci registrdə əməliyyat kodu, ikincidə isə ünvan var. RAM* üçün təlimatlar dəsti, dolayı ünvanlama istisna olmaqla, hər şeydə RAM üçün müvafiq dəstlə üst-üstə düşür, bu istisna olunur: RAM* proqramın icrası zamanı təlimatları dəyişdirərək dolayı ünvanlamanı simulyasiya edə bilər.

Tələbənin həll yolu kimi həyata keçirdiyi alqoritmin müəyyən ilkin məlumatlar verilməklə problemə düzgün cavab verməyə qadir olduğunu yoxlamaqla yanaşı, həll yolu yoxlanarkən proqramın işləmə müddəti də nəzərə alınır. Bu, istisnasız olaraq bütün tapşırıqlar üçün optimal alqoritmlərin yazılmasının həyati vacib olduğu anlamına gəlmir (bu, çox vaxt onların səriştəli icrası və sazlanması üçün çox vaxt tələb edə bilər). Bu, sadəcə olaraq o deməkdir ki, bəzi fərdi tapşırıqlarda vaxt parametri çox mühüm rol oynaya bilər. Ola bilər ki, olimpiadanın hansısa mərhələsində optimallığın zəruri olduğu bir problem də olmayacaq. Lakin bunun əksi də baş verə bilər.

Beləliklə, həm tələbələr, həm də müəllimlər müxtəlif alqoritmləri onların effektivliyinə görə müqayisə edə bilməlidirlər. Məktəblilər - lazımi anda bir problemi həll etmək üçün ən uyğun yolu seçmək üçün, müəllimlər - tapşırıqları bacarıqla seçmək və müəyyən bir problemin müəllifinin dəqiq belə vaxt məhdudiyyətləri təyin edərkən hansı həll yolunu düşündüyünü başa düşmək.

Alqoritmin effektivliyini qiymətləndirmək üçün O ilə işarələnmiş mürəkkəblik funksiyasından istifadə olunur (“böyük haqqında” oxuyun). Əslində, başqa qiymətləndirmələr də var, lakin tələbənin müxtəlif alqoritmlərlə yeni tanış olmağa başladığı mərhələdə onlara həqiqətən ehtiyac yoxdur. Mürəkkəblik funksiyası mənbə məlumatlarından və ya onların miqdarından asılı olaraq proqramın icra müddətinin artacağı nümunəni əks etdirir.

İcra müddəti ilkin verilənlərdən asılı olan alqoritmə misal olaraq N ədədinin bütün təbii bölənlərinin tapılması alqoritmini göstərmək olar. Aydındır ki, ədəd nə qədər böyükdürsə, bir o qədər çox dövrə addımlarını yerinə yetirmək lazım gələcək. İcra müddəti daxil edilən məlumatların miqdarından asılı olan alqoritm nümunəsi massivdə ən böyük ədədin axtarışı ola bilər. Massiv nə qədər uzun olsa, hansı ədədin ən böyük olduğunu müəyyən etmək üçün bir o qədər çox müqayisə əməliyyatları aparılmalıdır.

Əsas funksiyalar bunlardır:

l O(1) - belə mürəkkəblik funksiyası proqramın işləmə müddətinin istənilən ilkin verilənlər üçün sabit olduğunu göstərir;

l O(N) - əməliyyatların sayı N-ə mütənasib olaraq artır (burada N ya tapşırıq parametri, ya da massivdəki elementlərin sayı ola bilər).

l O(log N) - əməliyyatların sayı N loqarifmi ilə mütənasib olaraq artır (bu, məsələn, sifarişli massivdə elementi axtararkən yarılar metodunun mürəkkəbliyidir). N böyüklük sırası ilə artdıqca, əməliyyatların sayı bir dəyişir. Loqarifmin əsası adətən göstərilmir, bizi zamanın dəqiq dəyəri yox, böyümənin xarakteri (sürətli/yavaş) maraqlandırır.

l O(N2) - əməliyyatların sayı N-nin kvadratına mütənasib olaraq artır. Ümumiyyətlə, məsələnin mürəkkəbliyindən asılı olaraq O(Nk) ola bilər.

l O(N!) - əməliyyatların sayı faktorial N-ə mütənasib olaraq artır.

Burada bütün əməliyyatların eyni vaxtda yerinə yetirilmədiyinə görə bir sıra incəliklər var, ona görə də zamanın mürəkkəbliyini qiymətləndirərkən ən çox vaxt tələb edən əməliyyatlardan istifadə olunur.

Çox vaxt alqoritmləri təsvir edərkən onların iş vaxtının təxmini onun təmiz formada, yəni giriş/çıxış əməliyyatları nəzərə alınmadan verilir.

Misal: klaviaturadan massivə daxil olan və orada ən böyük elementi tapan proqramın mürəkkəbliyini qiymətləndirək.

N+(N-1)+1=2N əməliyyatlarının sayını əlavə edək. Yəni elə bir sabit var ki, istənilən N üçün əməliyyatların sayı CN-dən çox olmasın. Buna görə də alqoritmin mürəkkəbliyi O(N)-dir.

Misal: klaviaturadan massivə daxil olan və orada verilmiş xassə malik elementi tapan proqramın mürəkkəbliyini qiymətləndirək (məsələn, müəyyən qiymətə bərabər).

Alqoritm aşağıdakı addımlardan ibarətdir:

Verilmiş xassə ilə elementi axtaran massiv daxil etmək (N giriş əməliyyatı) (nə xoşbəxtdir: element ya massivin əvvəlinə yaxın, ya da ən sonunda yerləşə bilər; əgər element yoxdursa, onda siz bunu etməlisiniz. Buna əmin olmaq üçün bütün N müqayisələri aparın) nəticə çıxarın.

Ən yaxşı halda bu alqoritm üçün N+2 əməliyyatı (bütün massivin daxil edilməsi, tək müqayisə, çıxış), ən pis halda (belə element olmadıqda - 2N+1 əməliyyatları) tələb olunacaq. N böyük rəqəmdirsə, məsələn, təxminən 106, onda birliyə laqeyd yanaşmaq olar. Buna görə də alqoritmin mürəkkəbliyi O(N)-dir.

Nümunə: əvəzetmə metodundan istifadə etməklə L uzunluğunda sözün şifrələmə alqoritminin mürəkkəblik funksiyasını təyin edək. Əlifbanın hər simvolu üçün əvəz edilməli olan simvolun yazıldığı bir cədvəl olsun. S əlifbasının hərflərinin sayını qeyd edək.

Alqoritm aşağıdakı addımlardan ibarətdir:

Bütün simvollar arasında sözün (bir əməliyyat) daxil edilməsi

1. hər bir simvol üçün cədvəldə onun əvəzini tapın (əgər cədvəl sifariş olunmayıbsa və axtarışı asanlaşdıran heç bir xassə yoxdursa, ən pis halda, əgər axtarılan element ən yüksək nöqtədədirsə, bir simvol üçün S əməliyyatları var. son)

2. tapılmış simvolun çıxışı

Dövrün sonu

Əməliyyatların ümumi sayı 1+(S+1)*L-dir. Kifayət qədər böyük S və L vahidlərinə laqeyd yanaşmaq olarsa, məlum olur ki, bu alqoritmin mürəkkəblik funksiyası O(S*L) olur.

Nümunə: N natural ədədini ikilik say sisteminə çevirmək alqoritminin mürəkkəblik funksiyasını təyin edək (məlumatların daxil edilməsi və çıxışı əməliyyatları olmadan).

Alqoritm aşağıdakı addımlardan ibarətdir:

Ədədin 2-yə bölünməsinin nəticəsi 0 olana qədər döngə edin

1. ədədi 2-yə bölün və qalanı yadda saxlayın

2. bölmənin nəticəsini yeni ədəd kimi qəbul edin

Dövrün sonu

Əməliyyatların ümumi sayı 1+log2N-dən çox deyil. Buna görə də bu alqoritm O(log N) mürəkkəbliyinə malikdir.

Əgər proqram müxtəlif mürəkkəblik funksiyalarına malik bir neçə hissədən ibarətdirsə, o zaman O Daha böyük mürəkkəblik funksiyası kiçik olanları "udacaq". Məsələn, sifarişli massivin O(N) massivinin daxil edilməsini, O(N2) çeşidlənməsini və O(N) çıxışını edirsinizsə, onda bütün proqramın O(N2) mürəkkəbliyinə malik olduğunu deyə bilərsiniz.

Alqoritmlərin mürəkkəblik funksiyaları haqqında biliklərin praktiki tətbiqi ikitərəflidir. Birincisi, müəyyən bir tapşırıq üçün ədəbiyyatda bu barədə müvafiq məlumatlar varsa, daha optimal alqoritm seçilə bilər. İkincisi, bir ilkin məlumat toplusunda öz həllinin işləmə müddətini bilməklə, tələbə müəyyən bir problem üçün maksimum məhdudiyyətlərə uyğun gələn eyni proqramın işləmə müddətini təxminən təxmin edə bilər.

Suallar

Bu tapşırıqlar təqdim olunan material üzrə özünü sınamaq üçün istifadə olunur və məcburi deyil.

1. Kvadrat tənliyin həlli alqoritminin mürəkkəblik funksiyasını təyin edin.

2. Verilmiş tərəflərin sayı əsasında nizamlı çoxbucaqlının çəkilməsi alqoritminin mürəkkəblik funksiyasını təyin edin.

3. Verilmiş vəziyyətdə massivə element daxil etmək alqoritminin mürəkkəblik funksiyasını təyin edin (ədədləri verilmişdən çox və ya ona bərabər olan bütün elementlərin bir-bir sağa ilkin yerdəyişməsi ilə).

4. İki natural ədədin sütuna əlavə edilməsi alqoritminin mürəkkəblik funksiyasını təyin edin (A birinci ədədin rəqəmlərinin sayı, B ikincinin rəqəmlərinin sayı olsun).

5. Sütunda iki natural ədədin vurulması alqoritminin mürəkkəblik funksiyasını təyin edin.