Mavzu: Algoritmlar samaradorligini tahlil qilish. Reja: Samaradorlik ko’rsatkichlari

Kompyuter B ish vaqti (ichida.) nanosaniyalar)
16	8	100,000
63	32	150,000
250	125	200,000
1,000	500	250,000

Ushbu ko'rsatkichlarga asoslanib, shunday xulosaga kelish oson bo'lar edi Kompyuter A samaradorligi jihatidan ancha ustun bo'lgan algoritmni ishlaydi Kompyuter B. Ammo, agar kirish ro'yxati hajmi etarlicha ko'paytirilsa, bu xulosa keskin xatoga yo'l qo'yilganligini ko'rsatadi:

n (ro'yxat hajmi)	Kompyuter ish vaqti (ichida.) nanosaniyalar)	Kompyuter B ish vaqti (ichida.) nanosaniyalar)
16	8	100,000
63	32	150,000
250	125	200,000
1,000	500	250,000
...	...	...
1,000,000	500,000	500,000
4,000,000	2,000,000	550,000
16,000,000	8,000,000	600,000
...	...	...
63,072 × 10^12	31,536 × 10^12 ns, yoki 1 yil	1 375 000 ns, yoki 1,375 millisekund

Chiziqli qidiruv dasturini boshqaradigan A kompyuter, a ni namoyish etadi chiziqli o'sish sur'ati. Dasturning ishlash vaqti uning kirish hajmiga to'g'ri proportsionaldir. Kirish hajmini ikki baravar oshirish ish vaqtini ikki baravar oshiradi, kirish hajmini to'rt baravar oshirish ish vaqtini to'rt baravar oshiradi va hokazo. Boshqa tomondan, B ikkilik qidiruv dasturini ishga tushirgan kompyuter B a ni namoyish etadi logaritmik o'sish sur'ati. Kirish hajmini to'rt baravar oshirish faqat ish vaqtini a ga oshiradi doimiy miqdori (ushbu misolda, 50,000 ns). A kompyuter go'yoki tezroq mashina bo'lsa ham, B kompyuteri ish vaqtida muqarrar ravishda A kompyuterni ortda qoldiradi, chunki u o'sish sur'ati ancha past bo'lgan algoritm bilan ishlaydi.

O'sish tartiblari

Norasmiy ravishda algoritm a tartibida o'sish sur'atini namoyish etadi deyish mumkin matematik funktsiya agar ma'lum bir kirish hajmidan tashqarida bo'lsa n, funktsiyasi f(n) marta ijobiy konstantani ta'minlaydi yuqori chegara yoki chegara ushbu algoritmning ishlash muddati uchun. Boshqacha qilib aytganda, berilgan kirish hajmi uchun n ba'zilaridan kattaroq n₀ va doimiy v, bu algoritmning ishlash muddati hech qachon kattaroq bo'lmaydi . Ushbu kontseptsiya Big O notation yordamida tez-tez ifodalanadi. Masalan, ish vaqtidan beri qo'shish tartibi kvadratik ravishda o'sadi uning kirish hajmi oshgani sayin qo'shish tartibida deb aytish mumkin O(n²).

Big O notation - ifodalashning qulay usuli eng yomon stsenariy ma'lum bir algoritm uchun, garchi u o'rtacha holatni ifodalash uchun ham ishlatilishi mumkin bo'lsa ham - masalan, eng yomon stsenariy tezkor bu O(n²), lekin o'rtacha ish vaqti O(n jurnaln).

O'sishning ampirik buyurtmalari

Amalga oshirish vaqti kuch qoidalariga amal qiladi deb hisoblasak, t ≈ k n^a,

koeffitsient a topish mumkin ^[8] ish vaqtining empirik o'lchovlarini olish orqali {t_ {1}, t_ {2} }}

ba'zi bir muammo nuqtalarida {n_ {1}, n_ {2} }} va hisoblash t_ {2} / t_ {1} = (n_ {2} / n_ {1}) ^ {a} Shuning uchun; ... uchun; ... natijasida a = log (t_ {2} / t_ {1}) / log (n_ {2} / n_ {1}). Boshqacha qilib aytganda, bu empirik chiziqning moyilligini o'lchaydi log-log fitna bajarilish vaqti va muammoning kattaligi, ba'zi bir o'lchamdagi nuqtalarda. Agar o'sish tartibi chindan ham quvvat qoidasiga amal qilsa (va shuning uchun log-log uchastkasida chiziq to'g'ri chiziq bo'lsa), empirik qiymati a har xil diapazonlarda doimiy bo'lib qoladi va agar bo'lmasa, u o'zgaradi (va chiziq egri chiziq) - lekin shunga qaramay har qanday ikkita algoritmni taqqoslash uchun xizmat qilishi mumkin o'sishning ampirik mahalliy buyurtmalari xulq-atvor. Yuqoridagi jadvalga qo'llaniladi: