«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan Mustaqil ish

Kvazilinear vaqt

Agar algoritm agar kvazilinear vaqt ichida ishlaydi deyiladi T(n) = O ( n jurnal k n) baʻzi bir doimiy uchun k... Lineer-logaritmik vaqt - bu alohida holat k \u003d 1. Zaif-O yozuvidan foydalanganda ushbu algoritmlar Õ ( n). Kvazilinear vaqt algoritmlari ham o ( n Har qanday ε\u003e 0 uchun 1 + ε) va ichida har qanday polinomdan tezroq ishlaydi n

Yarim chiziqli vaqtda ishlaydigan algoritmlarga, yuqorida aytib oʻtilgan chiziqli-logaritmik algoritmlardan tashqari quyidagilar kiradi.

• 
  Joyida birlashtirish saralashi, O ( n jurnal 2 n)
  
• 
  Tez saralash, O ( n jurnal n), ehtimollik versiyasida eng yomon holatda chiziqli-logaritmik bajarish vaqti mavjud. Mumkin boʻlmagan versiyada oʻrtacha qiyinchilikni oʻlchash uchun chiziqli jurnalning ishlash vaqti mavjud.
  
• 
  Heapsort, O ( n jurnal n), birlashtirish sort, introsort, ikkilik daraxt sort, silliq saralash, jungle sort, va hokazo. eng yomoni
  
• 
  Tez Furye oʻzgarishi, O ( n jurnal n)
  
• 
  Mone matritsalarini hisoblash, O ( n jurnal n)