Algoritmlarni eng yomon va o‘rtacha holatlarda baholash. Asimptotik analiz. Algoritmlarni analiz qilish

Amaliy natijalar

Eng yomon yomon ko'rsatkichlarga ega bo'lgan ko'plab algoritmlar o'rtacha o'rtacha ko'rsatkichlarga ega. Biz hal qilmoqchi bo'lgan muammolar uchun bu yaxshi narsa: biz g'amxo'rlik qilayotgan ayrim holatlar o'rtacha deb umid qilishimiz mumkin. Uchun kriptografiya, bu juda yomon: biz kriptografik muammoning odatiy misollari qiyin bo'lishini xohlaymiz. Bu erda shunga o'xshash usullar tasodifiy o'z-o'zini kamaytirish eng yomon holat o'rtacha ishdan ko'ra qiyinroq emasligini yoki unga teng ravishda o'rtacha ish eng yomon ishdan osonroq emasligini ko'rsatadigan ba'zi bir aniq muammolar uchun ishlatilishi mumkin.
Boshqa tomondan, ba'zi ma'lumotlar tuzilmalari yoqadi xash jadvallar juda yomon holatlarga ega, ammo yaxshi hajmda yozilgan xash jadvali statistik jihatdan hech qachon eng yomon holatni keltirib chiqarmaydi; bajarilgan operatsiyalarning o'rtacha soni eksponensial parchalanish egri chizig'iga amal qiladi va shu sababli operatsiyani bajarish vaqti statistik jihatdan chegaralangan.

Misollar

Algoritmlarni saralash

Shuningdek qarang: Algoritmni saralash § Algoritmlarni taqqoslash

Algoritmlarni tahlil qilishda odatda ishlatiladigan funktsiyalar grafikalari, amallar sonini ko'rsatadi N kirish kattaligiga nisbatan n har bir funktsiya uchun

• 
  Kiritish tartibi ro'yxatiga qo'llaniladi n har xil va dastlab tasodifiy tartibda deb taxmin qilingan elementlar. O'rtacha ro'yxatdagi elementlarning yarmi A₁ ... A_j elementdan kamA_j+1va yarmi kattaroq. Shuning uchun algoritm (j + 1) o'rtacha element kiritilishi kerak bo'lgan element, allaqachon ajratilgan pastki ro'yxatning yarmi bilan, shuning uchun t_j = j/ 2. Olingan o'rtacha ish vaqtini ishlab chiqish, eng yomon ish vaqti kabi, kirish hajmining kvadratik funktsiyasini beradi.
  
• 
  Quicksort ro'yxatiga qo'llaniladi n elementlari, yana barchasi boshqacha deb taxmin qilingan va dastlab tasodifiy tartibda. Bu mashhur saralash algoritmi o'rtacha ish ko'rsatkichiga ega O (n log (n)), bu uning amalda juda tez algoritmga aylanishiga yordam beradi. Ammo eng yomon kirishni hisobga olgan holda, uning ishlashi O (n²). Bundan tashqari, "eng qisqa birinchi" siyosati bilan amalga oshirilganda, eng yomon kosmik murakkablik o'rniga O (log (n)).
  
• 
  Heapsortda barcha elementlar bir xil bo'lgan O (n) vaqt bor. Heapify O (n) vaqtni oladi va keyin yig'indagi elementlarni olib tashlash n elementlarning har biri uchun O (1) vaqt. Ishlash vaqti O (nlog (n)) gacha o'sadi, agar barcha elementlar bir-biridan farq qilishi kerak bo'lsa.
  
• 
  Bogosort elementlarning birinchi takrorlashda saralanishida O (n) vaqti bor. Har bir takrorlashda barcha elementlar tartibda tekshiriladi. N bor! mumkin bo'lgan almashtirishlar; muvozanatli tasodifiy sonlar generatori bilan massivning deyarli har bir almashinuvi n ga teng bo'ladi! takrorlash. Kompyuterlarning xotirasi cheklangan, shuning uchun hosil bo'lgan raqamlar aylanishi; har bir almashtirishga erishish mumkin bo'lmasligi mumkin. Eng yomon holatda bu O (() vaqtga, cheksiz pastadirga olib keladi.