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

Polilogaritmik vaqt

Algoritm ishlaydi deyiladi polilogaritmik vaqt, agar a T(n) \u003d O ((log.) n) k), baʻzi uchun k... Masalan, matritsani koʻpaytirish tartibi masalasi tomonidan polilogaritmik vaqt bilan parallel PAM mashinasi .

Sublinear vaqt

Algoritm ishlaydi deyiladi sublinear vaqt, agar a T(n) \u003d o ( n). Xususan, bunga yuqorida sanab oʻtilgan vaqt murakkabligi algoritmlari va boshqalar kiradi, masalan, O ( n ½).

Oddiy algoritmlar, aniq boʻlsa-da, hali ham chiziqli vaqt ichida ishlaydi, jarayonlarning parallellashuvidan foydalanadi (matritsaning determinantini hisoblash uchun NC 1 algoritmi kabi), klassik boʻlmagan hisob-kitoblar (Grover qidiruvida boʻlgani kabi) yoki tuzilish haqida kafolatlangan taxminlarga ega. kirish (logaritmik vaqtda ishlaydigan kabi, ikkilik qidiruv algoritmlari va koʻplab daraxtlarni qayta ishlash algoritmlari). Shu bilan birga, rasmiy konstruktsiyalar, masalan, satrning birinchi log (n) bitlari bilan belgilanadigan holatda 1 bitga ega boʻlgan barcha satrlar toʻplami, kirishning har bir bitiga bogʻliq boʻlishi mumkin, ammo vaqt oʻtishi bilan sublinear boʻlib qoladi.

Muddat sublinear algoritm odatda, yuqoridagi misollardan farqli oʻlaroq, odatiy ketma-ketlikdagi mashinalar modellarida ishlaydigan va kirish tuzilishi boʻyicha apriori bilimlarni talab qilmaydigan algoritmlar uchun ishlatiladi. Biroq, ular uchun ehtimollik usullaridan foydalanishga ruxsat beriladi va undan ham koʻpi, ahamiyatsiz muammolar uchun algoritmlar ehtimoliy boʻlishi kerak.

Bunday algoritm kirish maʻlumotlarini toʻliq oʻqimasdan javob berishi kerakligi sababli, u kirish oqimida ruxsat berilgan kirish usullariga juda bogʻliq. Odatda bir oz magʻlubiyatli oqim uchun b 1 ,...,b k, algoritm O (1) vaqt ichida qiymat soʻrashi mumkin deb taxmin qilinadi b i har kim uchun men.

Sublinear vaqt algoritmlari, qoida tariqasida, ehtimollikga ega va faqat taxminiy echimni beradi. Sublinear ish vaqti algoritmlari tergov paytida tabiiy ravishda paydo boʻladi mulkni tekshirish.