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

Logaritmik vaqt

Logaritmik vaqt, agar a T(n) = O (log n) ... Kompyuterlar ikkilik tizimdan foydalanganligi sababli, logarifmaning asosi sifatida 2 ishlatiladi (yaʻni log 2) n). Biroq, bilan bazani almashtirish logarifmlar log a n va jurnal b n faqat doimiy koeffitsient bilan farq qiladi, bu esa O katta yozuvida bekor qilinadi. Shunday qilib O (log n) - logaritma asosidan qatʻi nazar, logaritmik vaqt algoritmlari uchun standart yozuv.

Logaritmik vaqt algoritmlari odatda ikkilik daraxt operatsiyalarida yoki ikkilik qidiruvdan foydalanishda uchraydi.

O (log n) algoritmlari juda samarali hisoblanadi, chunki elementlar sonining koʻpayishi bilan har bir element uchun bajarilish vaqti kamayadi.

Bunday algoritmning juda oddiy misoli - bu satrni yarmiga boʻlish, qolgan yarmi yana yarmiga boʻlinishi va hk. Bu O (log n) vaqtni oladi (bu erda n - ipning uzunligi, biz bu erda deb oʻylaymiz console.log va str.substring doimiy vaqtni oling). Bu shuni anglatadiki, muhrlar sonini koʻpaytirish uchun chiziq uzunligini ikki baravar oshirish kerak.

// Qatorning oʻng yarmini rekursiv bosib chiqarish funktsiyasi var right \u003d funktsiya (str) (var uzunligi \u003d str. uzunlik; // yordamchi funktsiyasi var help \u003d funktsiya (indeks) { // Rekursiya: oʻng yarmini chop eting agar (indeks< length ) { // Belgilarni indeksdan satr oxirigacha chop eting konsol. log (str. substring (indeks, uzunlik)); // rekursiv chaqiruv: yordamchi funktsiyani oʻng tomon bilan chaqiring yordam (Math.ceil ((uzunlik + indeks) / 2)); )) yordam (0);