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

esa fayl hali ham ochiq: ruxsat bering n = fayl hajmi uchun har 100000 kishi kilobayt fayl hajmining oshishi ajratilgan xotira hajmini ikki baravar oshirish
Bunday holda, n hajmi kattalashgan sari xotira an da sarflanadi eksponent o'sish stavkasi, bu buyurtma O (2ⁿ). Bu xotira iste'moli uchun juda tez va ehtimol boshqarib bo'lmaydigan o'sish sur'ati resurslar.


Dolzarbligi

Algoritm tahlili amalda muhim ahamiyatga ega, chunki samarasiz algoritmdan tasodifiy yoki bexosdan foydalanish tizim ishiga sezilarli ta'sir ko'rsatishi mumkin. Vaqtni sezgir bo'lgan dasturlarda uzoq vaqt davomida ishlaydigan algoritm natijalarini eskirgan yoki foydasiz holga keltirishi mumkin. Shuningdek, samarasiz algoritm ishlash uchun tejashga yaroqsiz miqdordagi hisoblash quvvati yoki saqlashni talab qilib, uni deyarli foydasiz holga keltirishi mumkin.

Doimiy omillar
Algoritmlarni tahlil qilish odatda asimptotik ko'rsatkichlarga, xususan, boshlang'ich darajaga qaratiladi, ammo amaliy qo'llanmalarda doimiy omillar muhim ahamiyatga ega va haqiqiy ma'lumotlar amalda har doim ham cheklangan hajmga ega. Chegara odatda manzilli xotiraning o'lchamiga teng, shuning uchun 32-bitli mashinalarda 2³² = 4 GiB (agar katta bo'lsa segmentlangan xotira va 64-bitli mashinalarda 2)⁶⁴ = 16 EiB. Shunday qilib cheklangan kattalik berilgan holda, o'sish tartibi (vaqt yoki makon) doimiy omil bilan almashtirilishi mumkin va shu ma'noda barcha amaliy algoritmlar etarlicha katta doimiy yoki etarli bo'lmagan ma'lumotlar uchun O (1) dir.

Ushbu talqin birinchi navbatda juda sekin o'sadigan funktsiyalar uchun foydalidir: (ikkilik) takroriy logarifma (log^*) barcha amaliy ma'lumotlar uchun 5 dan kam (2⁶⁵⁵³⁶ bit); (ikkilik) log-log (log log.) n) deyarli barcha amaliy ma'lumotlar uchun 6 dan kam (2⁶⁴ bit); va ikkilik jurnal (log n) deyarli barcha amaliy ma'lumotlar uchun 64 dan kam (2⁶⁴ bit). Doimiy bo'lmagan murakkablikka ega algoritm, shunga qaramay, amaliy ma'lumotlarning doimiy murakkabligi bo'lgan algoritmga qaraganda samaraliroq bo'lishi mumkin, agar doimiy vaqt algoritmining ustuni katta doimiy omilga olib keladigan bo'Ladi.

Katta ma'lumotlar uchun chiziqli yoki kvadratik omillarni e'tiborsiz qoldirib bo'lmaydi, ammo kichik ma'lumotlar uchun asimptotik samarasiz algoritm samaraliroq bo'lishi mumkin. Bu, ayniqsa, ishlatiladi gibrid algoritmlar, kabi Timsort, unda asimptotik jihatdan samarali algoritm ishlatiladi (bu erda birlashtirish, vaqt murakkabligi bilan n log n), lekin asimptotik samarasiz algoritmga o'ting (bu erda qo'shish tartibi, vaqt murakkabligi bilan n^{2}) kichik ma'lumotlar uchun, chunki oddiyroq algoritm kichik ma'lumotlarda tezroq bo'ladi.