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

Lineer logaritmik vaqt

Lineer-logaritmik - bu koʻrsatkich bilan kvazilinear vaqtning maxsus hodisasidir k Logaritmik atama boʻyicha \u003d 1.

Lineer logaritmik funktsiya shaklning funktsiyasi n jurnal n (yaʻni mahsulot chiziqli va logaritmik atamalar). Algoritm uchun ishlaydi deyiladi chiziqli-logaritmik vaqt, agar a T(n) = O ( n jurnal n) ... Shunday qilib, chiziqli-logaritmik element chiziqli muddatdan tezroq oʻsadi, lekin har qanday polinomdan sekinroq n qatʻiy ravishda 1 dan katta darajaga ega.

Koʻpgina hollarda, ish vaqti n jurnal n shunchaki operatsiya natijasidir Θ (log n) n vaqt. Masalan, ikkilik daraxt bilan saralash har bir elementni n kattalikdagi massivga birma-bir kiritish orqali ikkilik daraxt hosil qiladi. Qoʻshish jarayoni beri muvozanatli ikkilik qidiruv daraxti O oladi (log n), algoritmning umumiy bajarilish vaqti chiziqli-logaritmik boʻladi.

Taqqoslash boʻyicha saralash hech boʻlmaganda eng yomon taqqoslashlarning chiziqli-logaritmik sonini talab qiladi, chunki log ( n!) = Θ( n jurnal n) Stirling formulasi boʻyicha. Xuddi shu ijro vaqti koʻpincha takrorlanish tenglamasidan kelib chiqadi T(n) = 2 T(n/ 2) + O ( n).