n (ro'yxat hajmi)
|
Kompyuter ish vaqti
(ichida.) nanosaniyalar)
|
O'sishning mahalliy tartibi
(n ^ _)
|
Kompyuter B ish vaqti
(ichida.) nanosaniyalar)
|
O'sishning mahalliy tartibi
(n ^ _)
| |
15
|
7
|
|
100,000
|
| |
65
|
32
|
1.04
|
150,000
|
0.28
| |
250
|
125
|
1.01
|
200,000
|
0.21
| |
1,000
|
500
|
1.00
|
250,000
|
0.16
| |
...
|
...
|
|
...
|
| |
1,000,000
|
500,000
|
1.00
|
500,000
|
0.10
| |
4,000,000
|
2,000,000
|
1.00
|
550,000
|
0.07
| |
16,000,000
|
8,000,000
|
1.00
|
600,000
|
0.06
| |
...
|
...
|
|
...
|
|
Birinchi algoritm haqiqatan ham kuch qoidasiga rioya qilgan holda o'sishning chiziqli tartibini namoyish etishi aniq ko'rinib turibdi. Ikkinchisining empirik qiymatlari tez pasayib bormoqda, demak, bu o'sishning yana bir qoidasiga amal qiladi va har qanday holatda ham o'sishning mahalliy tartiblari ancha past (va bundan keyin ham yaxshilanadi), birinchisiga qaraganda.
Ish vaqti murakkabligini baholash
Berilgan algoritmning eng yomon stsenariysi uchun ish vaqti murakkabligi ba'zan algoritmning tuzilishini o'rganish va ba'zi soddalashtirilgan taxminlarni kiritish orqali baholanishi mumkin. Quyidagilarni ko'rib chiqing psevdokod:
1 kirishdan n ning musbat tamsayıini oling2 agar n> 103 chop etish "Bu biroz vaqt olishi mumkin ..." 4 uchun i = 1 ga n5 uchun j = 1 ga i6 chop etish i * j7 chop etish "Bajarildi!"
Berilgan kompyuter a ni oladi diskret vaqt har birini bajarish uchun ko'rsatmalar ushbu algoritmni bajarish bilan bog'liq. Berilgan ko'rsatmani bajarish uchun ma'lum vaqt miqdori qaysi ko'rsatma bajarilayotganiga va qaysi kompyuter uni bajarayotganiga qarab o'zgaradi, ammo an'anaviy kompyuterda bu miqdor bo'ladi deterministik.[9] 1-bosqichda bajarilgan harakatlar vaqtni sarflaydi deb ayting T1, 2-qadam vaqtdan foydalanadi T2, va hokazo.
Yuqoridagi algoritmda 1, 2 va 7 bosqichlar faqat bir marta bajariladi. Eng yomon vaziyatni baholash uchun 3-qadam ham bajarilishini taxmin qilish kerak. Shunday qilib, 1-3 va 7-bosqichlarni bajarish uchun umumiy vaqt miqdori:
T_ {1} + T_ {2} + T_ {3} + T_ {7}. ,
The ko'chadan 4, 5 va 6-bosqichlarda hiyla-nayrangni baholash kerak. 4-bosqichda tashqi tsikl testi bajariladi ( n + 1) marta (for loopini tugatish uchun qo'shimcha qadam kerakligini unutmang, shuning uchun n + 1 emas, balki n) T4( n + 1) vaqt. Ichki halqa esa j qiymati bilan boshqariladi, bu takrorlanadi 1 dan men. Tashqi halqa orqali birinchi o'tish paytida j 1 dan 1 gacha takrorlanadi: Ichki tsikl bitta o'tishni amalga oshiradi, shuning uchun ichki halqa tanasini (6-qadam) ishlatish sarf qiladi T6 vaqtni va ichki pastadir sinovi (5-qadam) 2 ni sarflaydiT5 vaqt. Tashqi tsikldan keyingi o'tish paytida j 1 dan 2 gacha takrorlanadi: ichki tsikl ikkita o'tishni amalga oshiradi, shuning uchun ichki tsikl tanasini (6-qadam) boshqarishda 2 ta sarflanadiT6 vaqt, va ichki pastadir sinovi (5-qadam) 3ni iste'mol qiladiT5 vaqt.
Umuman olganda ichki tsikl korpusini ishlash uchun zarur bo'lgan umumiy vaqt an shaklida ifodalanishi mumkin arifmetik progressiya:
T_ {6} + 2T_ {6} + 3T_ {6} + cdots + (n-1) T_ {6} + nT_ {6} bo'lishi mumkin hisobga olingan[10] kabi
T_ {6} chap [1 + 2 + 3 + cdots + (n-1) + n o'ng] = T_ {6} chap [{ frac {1} {2}} (n ^ {2} + n) o'ng]
Tashqi tsikl sinovini o'tkazish uchun zarur bo'lgan umumiy vaqtni quyidagicha baholash mumkin:
{ begin {aligned} & 2T_ {5} + 3T_ {5} + 4T_ {5} + cdots + (n-1) T_ {5} + nT_ {5} + (n + 1) T_ {5 } = & T_ {5} + 2T_ {5} + 3T_ {5} + 4T_ {5} + cdots + (n-1) T_ {5} + nT_ {5} + (n + 1) T_ { 5} -T_ {5} end {hizalanmış}}}
bu faktordir
{ displaystyle { begin {aligned} va T_ {5} left [1 + 2 + 3 + cdots + (n-1) + n + (n + 1) right] -T_ {5} = & chap [{ frac {1} {2}} (n ^ {2} + n) o'ng] T_ {5} + (n + 1) T_ {5} -T_ {5} = & T_ {5} chap [{ frac {1} {2}} (n ^ {2} + n) o'ng] + nT_ {5} = & chap [{ frac {1} {2}} (n ^ {2} + 3n) o'ng] T_ {5} end {hizalangan}}}
Shuning uchun ushbu algoritm uchun umumiy ishlash vaqti:
f (n) = T_ {1} + T_ {2} + T_ {3} + T_ {7} + (n + 1) T_ {4} + chap [{ frac {1} {2}} (n ^ {2} + n) o'ng] T_ {6} + chap [{ frac {1} {2}} (n ^ {2} + 3n) o'ng] T_ {5}
qaysi kamaytiradi ga
f (n) = chap [{ frac {1} {2}} (n ^ {2} + n) o'ng] T_ {6} + chap [{ frac {1} {2}} (n ^ {2} + 3n) o'ng] T_ {5} + (n + 1) T_ {4} + T_ {1} + T_ {2} + T_ {3} + T_ {7}
Kabi bosh barmoq, har qanday funktsiyadagi eng yuqori tartibli muddat uning o'sish sur'atida hukmronlik qiladi va shu bilan ish vaqti tartibini belgilaydi deb taxmin qilish mumkin. Ushbu misolda n2 eng yuqori tartibli atama, shuning uchun f (n) = O (n) degan xulosaga kelish mumkin2). Rasmiy ravishda buni quyidagicha isbotlash mumkin:
Yana oqlangan ushbu algoritmni tahlil qilishga yondashish, deb e'lon qilish edi [T1..T7] barchasi bir birlik vaqtga to'g'ri keladi, shuning uchun tanlangan birliklar tizimida bitta birlik ushbu qadamlar uchun haqiqiy vaqtdan katta yoki teng bo'lishi kerak. Bu shuni anglatadiki, algoritmning ishlash vaqti quyidagicha buziladi:[11]
Boshqa resurslarning o'sish sur'atlari tahlili
Ish vaqtini tahlil qilish metodologiyasidan iste'molning o'sishi kabi boshqa o'sish sur'atlarini bashorat qilish uchun ham foydalanish mumkin xotira maydoni. Misol tariqasida, dastur hajmi bo'yicha xotiradan foydalanishni boshqaradigan va qayta taqsimlaydigan quyidagi psevdokodni ko'rib chiqing. fayl ushbu dasturni boshqaradigan:
Dostları ilə paylaş: |
