|
Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajmi bo‘yicha qiyinchiliklar
|
| bet | 9/9 | | Sana | 21.05.2024 | | Hajmi | 28,31 Kb. | | #247732 |
Bog'liq mustaqil ish2.2 Ova Ō - belgilar.
Vaqt murakkabligining xulq-atvorining tabiati ortib borayotganida N (N® ¥ ) chaqirdi algoritmning asimptotik murakkabligi.
Asimptotik murakkablikning o'sish tezligini tavsiflash uchun biz foydalanamiz O-notatsiyasi. Algoritmning vaqt murakkabligi tartibida deyilganda N2 :
T(N)= O(N2 )= O(f(N)),
Keyin musbat konstantalar borligi taxmin qilinadi C, n0 =const (C>0), hamma uchun shunday N ³ N0 tengsizlik amal qiladi
T(N) £ C* f(N)
Bu murakkablik bahosining yuqori chegarasi.
2-misol:
Mayli T (0) = 1, T (1) = 4, ..., T (N)=(N+1) 2, keyin bu algoritmning vaqt murakkabligi o'sish tartibida bo'ladi T(N)= O(N2 ).
Buni hamma uchun ko'rsatish mumkin N > n0 da n0 = 1, C = 4 tengsizlik (1) bajariladi.
(N+1)2 £ 4* N2
3-misol:
Vaqt murakkabligi polinom sifatida yozilsa
T(N)= C1 N2 + C2 N+ C3 ,
u holda bunday algoritm polinomning maksimal elementi darajasiga karrali murakkablik tartibiga ega, chunki u eng tez o'sadi. N® ¥ :
T(N)= O(N2 ).
Masalan:
3 n2 +5 n+1 £ 5 n2
" n ³ 1
Xulosa
Tyuring mashinasida arifmetik amallarni bajarish uchun tegishli algoritmlar bilan arifmetik amallarni almashtirish orqali ko‘p nomli vaqt algoritmiga keltirish mumkin. Yuqoridagi talablarning ikkinchisi bajarilmasa, bu endi to'g'ri bo'lmaydi. Butun son (Tyuring mashinasida n ga proportsional xotirani egallaydi) berilgan bo‘lsa, uni takroriy darajaga ko‘tarish yordamida n ta amalda hisoblash mumkin. Biroq, xotira ifodalash uchun ishlatiladi 2 2 n (\ displaystyle 2 ^ (2 ^ (n))), ga mutanosib 2 n (\ displaystyle 2 ^ (n)), va u kirish uchun ishlatiladigan xotiraga polinom emas, balki eksponensial jihatdan bog'liq. Demak, Tyuring mashinasida bu hisoblarni ko'pnomli vaqtda bajarish mumkin emas, lekin ko'p nomli arifmetik amallarni bajarish mumkin.
Aksincha, Tyuring mashinasining qadamlar sonida ishlaydigan, ikkilik kodli kiritishning polinom uzunligi bilan chegaralangan, lekin arifmetik amallar sonida ishlamaydigan, sonlar sonidagi polinom bilan cheklangan algoritmlar mavjud. kiritish. Bunga Evklidning ikkita butun sonning eng katta umumiy boʻluvchisini hisoblash algoritmi misol boʻla oladi.
|
| |
