|
Kvazilinear vaqt
Algoritm kvazizikli vaqtda ishlaydi, deyiladi, agar T(n) = O ( n jurnal k n) ba'zi doimiy uchun k... Chiziqli-logarifmik vaqt bilan alohida holat k= 1. Zaif-O belgilaridan foydalanilganda, bu algoritmlar Õ ( n). Kvazilinear vaqt algoritmlari ham o ( n 1 + e) har qanday e> 0 uchun va har qanday polinomdan tezroq ishlaydi n
Yuqorida aytib o'tilgan chiziqli-logarifmik algoritmlarga qo'shimcha ravishda, kvaziziiqli vaqtda ishlaydigan algoritmlarga quyidagilar kiradi:
O'z joyida birlashtirish tartibi, O ( n jurnal 2 n)
Tez tartiblash, O ( n jurnal n), ehtimolli versiyada eng yomon holatda chiziqli-logarifmik bajarilish vaqti mavjud. Mumkin bo'lmagan versiyada o'rtacha qiyinchilikni o'lchash uchun chiziqli jurnalning ishlash vaqti mavjud.
Uyumni tanlash, O ( n jurnal n), birlashma tartiblash, introsort, ikkilik daraxt tartibi, silliq tartiblash, solitaire turi, va hokazo. eng yomoni
Tez Furye o'zgarishi, O ( n jurnal n)
Monge matritsalarini hisoblash, O ( n jurnal n)
Dostları ilə paylaş: |
