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

1000 ta element chiziqli qidirish uchun 1000 ta tekshiruv kerak boʻladi, ikkilik esa kerak boʻladi jami 10! Farqi allaqachon 100 baravar! Eʻtibor bering: massivdagi elementlar soni 100 baravar koʻpaygan (10 dan 1000 gacha), ikkilik qidiruv uchun zarur boʻlgan tekshirishlar soni atigi 2,5 baravar koʻpaygan - 4 dan 10 gacha. 10000 element, farq yanada dramatik boʻladi: 10000 qatorni qidirish tekshiruvi va jami 14 chek ikkilik uchun. Va yana: elementlar soni 1000 baravar koʻpaygan (10 dan 10 000 gacha), cheklar esa atigi 3,5 baravar (4 dan 14 gacha) oshgan. Ikkilik qidirish algoritmining murakkabligi logaritmikdir, yoki Big-O notation-dan foydalanish uchun, - O (log n)... Nima uchun bu shunday nomlangan? Logaritma - eksponentatsiyaning teskarisi. Ikkilik logaritma 2 ning quvvatini hisoblash uchun ishlatiladi. Masalan, bizda 10000 ta element bor, ularni ikkilik qidirish bilan takrorlashimiz kerak.
Endi sizning koʻzingiz oldida rasm bor va bilasizki, buning uchun maksimal 14 ta tekshiruv kerak. Ammo sizning koʻzingiz oldida rasm boʻlmasa va kerakli tekshiruvlarning aniq sonini hisoblashingiz kerak boʻlsa-chi? Oddiy savolga javob berish kifoya: olingan natija\u003e \u003d tekshirilayotgan elementlar soni boʻlishi uchun 2 raqami qanday darajaga koʻtarilishi kerak? 10000 uchun bu 14-daraja boʻladi. 2-dan 13-gacha boʻlgan kuch juda oz (8192) Ammo 2 14 kuchga \u003d 16384 ga teng, bu raqam bizning shartimizni qondiradi (u\u003e \u003d massivdagi elementlar soni). Biz logaritmani topdik - 14.