ZAMONAVIY DASTURLASH TILLARI

5-MAVZU: ALGORITMLAR TAHLIL

1. O’rtacha holat
Tahlil nima?
Algoritm tahlilini, qo’yilgan masalani ushbu algoritm bilan yechish qancha vaqt talab qilishi deb tasavvur qilish mumkin.
Har bir qaralayotgan algorimtni N o’lchovli boshlang’ich ma’lumotlar massividagi masalalaning qanchalik tez yechilishi bilan baholaymiz.
Masalan, saralash algoritmi N ta qiymatdan iborat ro’yxatni o’sish tartibida joylashtirish uchun qancha taqqoslash talab qiladi yoki N*N o’lchamli ikkita matritsani ko’paytirishda qancha arifmetik amallar zarurligini hisoblash.
Bitta masalani turli algoritmlar bilan yechish mumkin. Algoritmlar tahlili bizga algoritmni tanlash uchun qurol bo’ladi. To’rtta qiymatdan eng kattasini tanlaydigan ikkita algoritmni qaraymiz:
largest = a
if b > largest then
largest = b
end if
return a
if s > largest then
largest = s end if if d > largest then
largest = d end if return largest
if a > b then if a > s then I f a > d then
return a else
return d end if else
if s > d then
return s else
return d end if end if else
if b > s then if b > d then
return b else
return d end if else
if s > d then
return s else
return d end if end if end if

Kо’rinib turibdiki, qaralayotgan algoritmlarning har birida uchta taqqoslash bajariladi. Birinchi algoritmni о’qish va tushunish oson, ammo kompyuterda bajarilish nuqtai nazaridan ularning murakkablik darajalari teng. Bu ikki algoritm vaqt nuqtai nazaridan teng, lekin birinchi algoritm largest nomli qo’shimcha o’zgaruvchi hisobiga ko’proq xotira talab qiladi. Agarda son yoki belgilar taqqoslansa, ushbu qo’shimcha o’zgaruvchi katta ahamiyatga ega bo’lmaydi, lekin boshqa turdagi ma’lumotlar bilan ishlaganda bu muhim ahamiyatga ega. Kо’plab zamonaviy dasturlash tillari katta va murakkab obyektlarni yoki yozuvlarni taqqoslash operatorlarini aniqlash imkonini beradi. Bunday hollarda qo’shimcha o’zgaruvchilarni joylashtirish katta joy talab qiladi. Algoritmlarning effektivligini tahlili qilishda bizni birinchi navbatda vaqt masalasi qiziqtiradi, ammo xotira muhim rol o’ynaydigan vaziyatda uni ham muhokama qilamiz.
Algoritmlaring turli xossalari bitta masalani yechuvchi ikki turdagi algoritmlarning effektivligini taqqoslash uchun xizmat qiladi.
Biz shuning uchun hech qachon matritsalarni ko’paytirish algoritmi bilan saralash algoritmini emas, balki ikkita turli saralash algoritmlarini bir-biri bilan taqqoslaymiz.
Algoritm tahlilining natijasi – belgilangan algoritmning kompyuterdan qancha vaqt yoki takrorlash talab qilishini aniq hisoblovchi formula emas.
Bunday ma’lumot muhim emas, bu holatda kompyuter turi, u bitta yoki undan ortiq foydalanuvchi tomonidan ishlatilyaptimi, uning protsessori va chastotasi qanaqa, protsessor chipida komandalar to’liqmi va kompilyator bajarilayotgan kodni qay darajada amalga oshirmoqda kabi tomonlarni nazarda tutish kerak.
Bu shartlar algoritm bajarilish natijasida dasturning ishlash tezligiga ta’sir qiladi. Yuqoridagi shartlar hisobiga dasturni boshqa tez ishlaydigan kompyuterga o’tkazilganda algoritm yaxshi ishlaganday bajarilishi tezroq amalga oshadi. Aslida esa unday emas, biz shuning uchun tahlilimizda kompyuterning imkoniyatlarini inobatga olmaymiz.
Oddiy va katta bо’lmagan dasturlarda bajariladigan amallar sonini N ning funksiyasi kо’rinishida aniq hisoblash mumkin.
Aksariyat holatlarda bunga zaruriyat qolmaydi. 8 .4 § da keltirilgan N + 5 ta va N + 250 ta amal bajariladigan ikki algoritm orasida N ning yetarlicha katta qiymatlarida deyarli farq bо’lmaydi. Shunga qaramay, biz algoritmlarni bajariladigan amallar soniga qarab tahlil qilamiz.
Algoritm tomonidan bajariladigan jarayonlar borki, biz ularning hammasini hisoblab o’tirmaymiz, buning sababi shundaki, hatto uning eng kichik sozlashi ham samaradorlikning sezilmas yaxshilanishiga olib keladi. Fayldagi turli belgilar sonini hisoblovchi algoritmni qaraymiz. Bu masala yechimi uchun algoritmning taxminiy ko’rinishi quyidagicha bo’ladi:
for all 256 belgilarni do hisoblagichni nolga tenglash end for while agar faylda belgi qolsa do navbatdagi belgini kо’rsat va hisoblagichni bittaga oshir end while do hisoblagichni nolga tenglashtirish end for while faylda belgi mavjud bо’lsa do navbatdagi belgini kо’rsat va hisoblagichni bittaga oshir end while
Ushbu algoritmni ko’rib chiqamiz. U takrorlanish bajarilishida 256 ta o’tish qiladi. Agar berilgan faylda N ta belgi bо’lsa unda ikkinchi takrorlanishda N ta o’tish qilinadi. «Bu qanday hisoblash?» degan savol tug’iladi. For siklida avval sikl о’zgaruvchisi bajariladi, keyin xar bir о’tishda uning sikl chegarasidan chiqmayotganligi tekshiriladi va о’zgaruvchi qiymatini oshiradi. Bu esa sikl bajarilishida 257 yuklash bajariladi (biri sikl о’zgaruvchisi, 256 tasi hisoblagich uchun), ya’ni 256 ta oshirish va 257 ta sikl chegarasidan chiqmaganligini tekshirish (bitta amal siklni tо’xtatish uchun qо’shilgan). Ikkinchi siklda N + 1 marta shart tekshiriladi (+1 fayl bо’sh bо’lgandagi oxirgi tekshiruv), va N hisoblagichni oshirish. Jami amallar:

Oshirish	N + 256
Yuklash	257
Shartlarni tekshirish	N + 258

Shunday qilib 500 belgidan iborat fayl berilsa algoritmda 1771 ta amal bajariladi, ulardan 770 tasi natija beradi (43%). Endi N ning qiymati oshganda nima bo’lishini ko’ramiz. Agar fayl 50 000 belgidan iborat bо’lsa, unda algoritm 100 771 amal bajaradi, ularning 770 tasi natija uchun (jami amallar sonining 1% ini tashkil etadi). Yechimga qaratilgan amallar soni oshmayapti, lekin N katta bo’lganda ularning foizi juda kam.
Endi boshqa tomoniga e’tibor qaratamiz. Kompyuterda ma’lumotlar bilan shunday ishlashga mо’ljallanganki, katta xajmdagi ma’lumotlar blokini kо’chirish va yuklash bir xil tezlikda amalga oshiriladi. Shuning uchun biz avval 16 ta hisoblagichga boshlang’ich qiymat 0 ni yuklaymiz, keyin qolgan hisoblagichlarni to’ldirish uchun shu blokdan 15 ta nusxa olamiz. Bu esa sikl bajarilish davomida tekshirishlar sonini 33 ga, yuklashlar sonini 33 va oshirishlar sonini 31 ga kamayishiga olib keladi. Demak amal bajarilishlar soni 770 dan 97 gacha kamaydi, ya’ni 87%. Agar erishilgan natijani 50000 belgidan iborat fayl ustida bajarsak, tejamkorlik 0.7% ni tashkil qiladi (100771 ta amal о’rniga 100098 amal bajaramiz).
Agarda barcha amallarni sikldan foydalanmay 31 ta yuklashlar orqali bajarganimizda, vaqtni yanada tejagan bo’lardik, ammo bu usul 0.07 foyda keltiradi. Ishimiz unumli bo’lmaydi.
Ko’rib turganimizdek, algoritmning bajarilish vaqti bilan bog’liq barcha amallar befoyda. Tahlil tili bilan aytganda, boshlang’ich ma’lumotlar hajmining ortishiga aloxida e’tibor qaratish kerak.
Avvalgi ishlarda algoritmlarni tahlil qilishda algoritmlarni Tyuring mashinasida hisoblash aniqlangan. Tahlilda masalani yechish uchun zarur bo’lgan o’tishlar soni hisoblangan. Bu turdagi tahlil tо’g’ri bo’lib, ikki algoritmning nisbiy tezliklarini aniqlash imkonini beradi, ammo uning amaliyotda qo’llanilishi kam, chunki ko’p vaqt talab qiladi. Avval bajariladigan algoritmning Tyuring mashinasidagi o’tish funksiyalarini yozish, keyin esa bajarilish vaqti hisoblanadi.
Algoritmlarni tahlil qilishning boshqa yaxshiroq usuli - uni biror yuqori bosqichli til Pascal, C, C++, JAVA da yozish yoki oddiy psevdokodlarda yozishdir. Barcha algoritmlarning asosiy boshqaruv strukturasini ifodalaganda psevdokodlarning xossalari ahamiyatga ega emas. Ixtiyoriy til bizning talabimizga javob beradi, chunki for yoki while shaklidagi sikllar, if, case yoki switch kо’rinishidagi tarmoqlanish mexanizmlari barcha dasturlash tillarida mavjud. Har gal biz bitta aniq algoritmni ko’rib chiqishimizga to’g’ri keladi – unda birdan ortiq funksiya yoki programma fragmenti kiritilgan bo’ladi, shuning uchun yuqorida keltirilgan tillarning tezligi umuman muhim emas. Psevdokodlardan foydalanishimizning sababi shunda.
Ko’plab dasturlash tillarida mantiqiy ifodaning qiymatlari qisqartirilgan shaklda hisoblanadi. Bu A and V ifodadagi V hadning qiymati qachonki A rost bo’lsagina hisoblanadi, aks holda natija V ga bog’liq bo’lmagan tarzda yolg’on bo’ladi. Xuddi shunday A or V ifodada A ning qiymati rost bo’lsa, V hadning qiymati hisoblanmaydi. Ko’rinib turibdiki, murakkab shartlarning 1 yoki 2 ga tengligidagi taqqoslashlarining sonini hisoblash shart emas. Shuning uchun bu bobni o’rganishda mantiqiy ifodalarning qiymatini qisqartirib hisoblanishini e’tiborsiz qoldiramiz.
Kiruvchi berilganlar sinfi
Algoritmlarning tahlilida kiruvchi ma’lumotlarning roli yuqori, chunki algoritm harakatlarining ketma-ketligi kiruvchi ma’lumotlar bilan belgilanadi. Masalan, N ta elementdan tashkil topgan ro’yxatning eng katta elementini topish uchun quyidagi algoritmdan foydalanish mumkin:
largest = list   [l]
for i = 2 to N do
if   (list   [i]   > largest) then
largest = list[i]
end if
end for

Agar ro’yxat kamayish tartibida bo’lsa, u holda sikl boshlanishidan avval bitta o’zlashtirish bajariladi, sikl tanasida esa o’zlashtirish bo’lmaydi. Agar rо’yxat o’sish tartibida bo’lsa, u holda N ta o’zlashtirish bajariladi (sikl boshlanishidan avval bitta va N-1 ta siklda). Biz tahlil qilish davomida kiruvchi qiymatlar to’plamining turli imkoniyatlarini ko’rib chiqishimiz kerak, agar bitta to’plam bilan chegaralansak, bu yechim eng tez (yoki eng sekin) bo’lgan to’plam bo’lib chiqishi mumkin. Natijada biz algoritm haqidagi yolg’on tasavvurga ega bo’lamiz. Buning o’rniga kiruvchi to’plamlar turining barchasini ko’rib chiqamiz.
Biz kiruvchi to’plamlarni har bir to’plamdagi algoritm holatiga bog’liq holda sinflarga bo’lib chiqamiz. Bunday bo’linish ko’rib chiqilayotgan to’plamlar miqdorini kamaytirish imkonini beradi. Masalan, 10 ta sondan iborat ro’yxat uchun eng katta elementni topish algoritmini qo’llaymiz. Birinchi soni eng katta bo’lgan 362 880 kiruvchi to’plamlar mavjud, ularni bitta sinfga joylashtirish mumkin. Agar qiymati bo’yicha eng katta son ikkinchi o’rinda turgan bo’lsa, u holda algoritm ikkita o’zlashtirishni amalga oshiradi. Eng kata son ikkinchi o’rinda turgan to’plam 362 880. Ularni boshqa sinfga kiritish mumkin. 1 dan N gacha bo’lgan sonlar orasida eng katta sonning o’zgarish holida o’zlashtirishlar sonining qanday o’zgarishini ko’rishimiz mumkin.
Shunday qilib, barcha kiruvchi to’plamlarni bajarilgan o’zlashtirishlar soni bo’yicha N ta turli sinfga bo’lish kerak. Ko’rib turganingizdek, har bir sinfda joylashgan to’plamlarni birma-bir yozish yoki yozib olish shart emas. Faqatgina har bir tо’plamdagi sinflar miqdori va ish hajmini bilish yetarli.
Kiruvchi berilganlarning mumkin bo’lgan to’plami N kattalashganda judayam katta bo’lishi mumkin. Masalan, 10 ta turli soni ro’yxatda 3 628 800 usulda joylashtirish mumkin. Bu usullarning barchasini ko’rib chiqishning imkoni yo’q. Biz buning o’rniga algoritm bajarilishiga ko’ra ro’yxatni sinflarga bo’lamiz. Yuqorida ko’rsatilgan algoritm uchun bo’linish eng katta qiymatning joylashishi o’rniga asoslanadi. Natijada 10 ta turli sinf hosil bo’ladi. Boshqa algoritm uchun, masalan, eng katta va eng kichik sonni topish algoritmida bо’linish eng katta va eng kichik sonning joylashuviga asoslanadi. Bunday bo’linishda 90 ta sinf bo’ladi. Sinflarni ajratib bo’lgach, har bir sinfdan bitta to’plamda algoritm holatini ko’rish mumkin. Agar sinflar tо’g’ri tanlangan bo’lsa, u holda bir sinfdagi kiruvchi berilganlar to’plamida algoritm bir xil miqdordagi amallarni bajaradi, boshqa sinfning to’plamlari uchun esa amallar miqdori boshqacha bo’ladi.
Xotira bо’yicha murakkablik
Biz asosan algoritmlarning vaqt bo’yicha murakkabligini muhokama qilamiz, ammo ish bajarish uchun u yoki bu algoritmga qancha xotira kerakligi haqida ham aytish mumkin. Kompyuter xotirasi (ham ichki, ham tashqi) hajmi chegaralangan. Kompyuterlar rivojlanishining dastlabki bosqichlarida bu tahlil uslubiy xarakterga ega edi. Barcha algoritmlar chegaralangan xotira yetarli yoki qo’shimcha maydonni talab qiluvchi algoritmlarga bo’linadi. Kо’pincha dasturlovchilar xotirasiga ega va tashqi qurilmalar talab qilmaydigan sekin ishlovchi algoritmni tanlashar edi.
         Kompyuter xotirasiga bо’lgan talab juda katta edi, shuning uchun qaysi ma’lumotlar saqlanib qoladi, bunday saqlashning samarali usullari qanday kabi savollar o’rganilar edi. Faraz qilaylik, masalan, biz -10 dan +10 gacha intervaldagi verguldan keyin bitta o’nli belgiga ega bo’lgan moddiy son yozyapmiz. Moddiy soni yozishda ko’pchilik kompyuterlar 4 dan 8 baytgacha xotira sarflaydi, leki nagar bu soni avvaldan 10 ga ko’paytirsak, -100 dan +100 gacha intervaldagi butun son hosil qilamiz va uni saqlash uchun bor yo’g’i bir bayt sarflanadi. Birinchi variant bilan solishtirsak, 3-7 bayt tejashga erishildi. 1000 ta shunday son saqlaydigan dastur 3000 dan 7000 baytgacha tejaydi. Agar o’tgan asrning 80-yillarida kompyuterlarning xotirasi 65536 bayt bo’lganligini e’tiborga olsak, jiddiy tejash ko’zga tashlanadi. Aynan shu kompyuter dasturlarining uzoq yil ishlashi xotirani tejash zaruriyati Bilan bir qatorda 2000 yil muammo tug’dirdi. Agar sizning dasturingiz turli sanalardan foydalansa, yilni yozish uchun 1999 o’rniga 99 ifodasini saqlagan holda joyning yarmini tejasa bo’ladi. 80-yillardagi dastur mualliflari mahsulotlari 2000 yilgacha yashashini taxmin ham qilishmagan edi.
         Hozirgi kunda bozorlarda taklif qilinayotgan dasturiy ta’minotga nazar tashlasak, xotiraning bunday tahlili o’tkazilmaganligi ayon bo’ladi. Oddiy dasturlar uchun zarur xotira hajmi megabaytlarda o’lchanadi. Dastur tuzuvchilar joyni tejash ehtiyojini his qilmayotganga o’xshaydilar, ularning fikricha, agar foydalanuvchida yetarli xotira bo’lmasa, u dastur bajarilishi uchun yetmayotgan 32 yoki undan ortiq megabayt xotira yoki uni saqlash uchun yangi qattiq disk sotib oladi. Natijada kompyuterlar o’zining belgilangan muddatidan avval yaroqsiz holga kelib qoladi.
         Yaqinda tarqalgan cho’ntak kompyuterlari (PDA – personal digital assistant) yangi ohang olib kirdi. Bunday qurilmaning xotirasi ham ma’lumotlar, ham dasturlar uchun 2 dan 8 megabaytgacha. Shuning uchun ham ma’lumotlarni ixcham saqlashni ta’minlovchi kichik dasturlarni yaratish qiyin bo’lib qolmoqda.

Nimani hisoblash va nimani inobatga olish lozim
Nimani hisoblash masalasi ikkita qadamdan iborat. Birinchi qadamda ahamiyatli jarayon yoki jarayonlar guruhi tanlanadi, ikkinchi qadamda shu jarayonlardan qay biri algoritmda joylashgan, qaysilari esa qo’shimcha harajatlarni yoki ma’lumotlarni qayd eti shva hisobga olishga ketishi tashkil etadi. Ikki xil ahamiyatli jarayon turi mavjud: taqqoslash va arifmetik amallar. Barcha taqqoslash operatorlari ekvivalent hisoblanadi va ularni izlash hamda ajratuv algoritmlarida inobatga olinadi. Taqqoslash miqdori bunday algoritmlarning muhim elementi hisoblanadi, izlashda ushbu miqdor izlangan kattalik bilan mos tushadimi, saralashda esa berilgan oraliqdan chiqishi aniqlanadi. Solishtiruvchi operatorlar bir kattalikning ikkinchisi bilan teng yoki teng emasligi, katta yoki kichikligi, kichik yoki tengligi, katta yoki tengligini tekshiradi.
Biz arifmetik amallarni ikki guruhga bо’lamiz: additiv va multiplikativ. Additiv operatorlar (qisqa qilib aytganda qo’shuv) qo’shish, ayirish, orttirish va qisqartirishni o’z ichiga oladi. Multiplikativ operatorlar (yoki qisqacha ko’paytirishlar) ko’paytirish, bo’lish va modul bo’yicha qoldiq olishni o’z ichiga oladi. Ikki guruhga ajratish ko’paytirishning qo’shishdan ko’proq ishlatilishiga bog’liq. Amaliyotda ba’zi algoritmlar ularda ko’paytirish kam bo’lsa, qo’shishlar soni proporsional darajada o’ssa ham afzalroq hisoblanadi. Biz о’z kitobimizda yana bir, ko’paytirishdan ham ko’p vaqt talab qiluvchi amallar guruhini hosil qiluvchi logarifmlar va trigonametrik funksiyalardan foydalanuvchi algoritmlarga to’xtalmadik (odatda kompyuterlar bu ifodalarni bir qatorga ajratish yordamida hisoblaydilar). Butun sonli ikki darajaga ko’paytirish yoki bo’lish alohida holatni tashkil qiladi. Bu jarayon siljishga olib keladi, keyingisi esa tezlik jihatdan qo’shishning ekvivalenti hisoblanadi. Biroq, bu tafovut sezilarli bо’lgan hollar juda kam, chunki 2 ga ko’paytirish va bo’lish birinchi navbatda taqqoslash operatorlari ahamiyatga ega bo’lgan «taqsimla va boshqar» singari algoritmlarda uchraydi.
Kiruvchi ma’lumotlarning sinflari
Algoritmni tahlil qilishda kiruvchi ma’lumotlarni tanlash uning bajarilishiga ta’sir qilishi mumkin. Aytaylik, ba’zi saralash algoritmlari, agar kirish ro’yxati saralangan bo’lsa, juda tez ishlashi mumkin, boshqa algoritmlar shunday ro’yxatda uncha katta bo’lmagan natijani ko’rsatadi. Tasodifiy ro’yxatda esa natija buning teskarisi bo’lishi mumkin. Shuning uchun biz ma’lumotlarning bir kirish ro’yxatidagi algoritmlar harakatini tahlil qilish bilan chegaralanmaymiz. Biz algoritmni ham eng tez, ham eng sekin ishlashini ta’minlovchi ma’lumotlarni qidiramiz. Bundan tashqari, biz barcha mavjud ma’lumotlar to’plamidagi algoritmlarning o’rtacha samarasini ham baholaymiz.
Eng yaxshi holat
Bo’limning nomlanishidan ham ko’rinib turibdiki, algoritmlar uchun eng yaxshi holat bu qisqa vaqt ichida amalga oshiriladigan algoritmning ma’lumotlar jamlanmasi. Bunday jamlanma algoritm eng amal bajaradigan qiymatlar kombinatsiyasini ifodalaydi. Agar biz izlash algoritmini tekshirsak, izlangan qiymat birinchi algoritm tekshirayotgan katakka yozilgan bo’lsa (odatda maqsadli qiymat yoki kalit deb ataladi), ma’lumotlar to’plami eng yaxshi hisoblanadi. Bunday algoritmga uning murakkabligidan qatiy nazar, bitta taqqoslash kerak bo’ladi. Shuni eslatish kerakki, ro’yxatdan izlashda, uning qanchalik uzun bo’lishidan qatiy nazar, eng yaxshi holat doimiy vaqtni talab qiladi. Umuman, eng yaxshi holatda algoritmni bajarish vaqti kichik yoki doimiy bo’ladi, shuning uchun biz bunday tahlilni kam o’tkazamiz.
Eng yomon holat
Eng yomon holatni tahlil qilish juda muhim, chunki u algoritm ishining maksimal vaqtini tasavvur qilishga yordam beradi. Eng yomon holatni tahlil qilganda algoritm eng ko’p ish bajaradigan kirish ma’lumotlarini topish zarur. Izlovchi algoritm uchun bu kabi kiruvchi ma’lumotlar – bu shunday ro’yxatki, unda izlangan kalit oxirida keladi yoki umuman bo’lmaydi. Natijada N taqqoslash kerak bo’ladi. Eng yomon holatning tahlili tanlangan algoritmga qarab dasturning ishlash vaqti uchun yuqori bahoni beradi.
O’rtacha holat
O’rta holatning tahlili eng murakkab hisoblanadi, chunki u ko’pgina detallarni hisobga olishni talab qiladi. Tahlil asosini mavjud bo’lgan kiruvchi ma’lumotlar to’plamini bo’lib chiqish lozim bo’lgan turli guruhlarni aniqlash tashkil qiladi. Ikkinchi qadamda kiruvchi ma’lumotlar to’plami qaysi guruhga tegishli bo’lish ehtimoli aniqlanadi. Uchinchi qadamda har bir guruhdagi ma’lumotlarga algoritmning ish vaqti hisoblanadi. Algoritmning bir guruhdagi hamma kiruvchi ma’lumotlar uchun ishlash vaqti bir xil bo’lishi kerak, aks holda guruhni bo’lish lozim. O’rtacha ish vaqti

formula orqali hisoblanadi. Bu yerda n - kiruvchi ma’lumotlar o’lchami, m - guruhlar soni, p_i - kiruvchi ma’lumotlarning i sonli guruhga tegishlilik ehtimoli, t_i– i sonli guruhdagi ma’lumotni qayta ishlash uchun algoritmga kerak bo’ladigan vaqt deb belgilangan.
Ba’zi hollarda biz kiruvchi ma’lumotlarning har bir guruhga tushish ehtimolini bir Xill deb taxmin qilamiz. Boshqacha aytganda, agar guruh 5 ta bo’lsa, birinchi guruhga tushish extimoli ikkinchi yoki boshqa guruhga tushish extimolidek, ya’ni har bir guruhga tushish extimoli 0,2 ga teng. Bu holda ishning o’rtacha vaqtini avvalgi formula Bilan yoki unga ekvivalent soddalashtirilgan barcha guruhlarning teng extimolligida haqiqiy bo’lgan

Misol. Misol tariqasida faylda N butun sonlar uchliklar sonini hisoblovchi ThreeSum dasturini olamiz. matnli kiruvchi ma’lumot sifatida 1Mints.txt faylini olamiz. [1]
1Kints.txt, 2Kints.txt, 4Kints.txt va 8Kints.txt faylli mos ravishda 1Mints.txt dagi 1000, 2000, 4000 va 8000 sondan iborat ThreeSum dasturini bajarishni birinchi mashqi sifatida shaxsiy kompyuteringizda bajarib ko’ring. Siz 1Kints.txt faylda nolinchi yig’indi bilan 70 ta uchlik, 2Kints.txt faylda esa 528 ta shunday uchliklar mavjud ekanligini bilib olasiz. Dasturda 4Kints.txt fayldagi nolinchi yig’indi bilan 4039 uchlikni hisoblashga ko’p vaqt talab etiladi. Tabiiyki, sizda dasturda 8Kints.txt fayldagi uchliklarni hisoblashga qancha vaqt ketadi degan savol tug’iladi? B savolga javob topish qiyin emas. Dastur bajarilishiga ketadigan aniq vaqtni ko’rsatish qiyin emas.