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

Logaritmik murakkablik

Vahima qoʻymang! :) Agar "logaritmik" soʻzi bilan siz maʻruzani yopmoqchi boʻlsangiz va boshqa oʻqimasangiz - bir necha daqiqa kuting. Bu erda hech qanday matematik qiyinchiliklar boʻlmaydi (bunday tushuntirishlar boshqa joylarda ham toʻliq) va biz barcha misollarni "barmoqlar ustida" tahlil qilamiz. Tasavvur qiling, sizning vazifangiz 100 ta raqamdan iborat qatorda bitta aniq sonni topishdir. Aniqrogʻi, u erda umuman yoʻqligini tekshirib koʻring. Kerakli raqam topilishi bilanoq, qidiruvni toʻxtatish kerak va "Kerakli raqam topildi! Uning massivdagi koʻrsatkichi \u003d .... ”Bunday muammoni qanday hal qilasiz? Bu erda yechim aniq: siz navbatma-navbat qator elementlari ustidan birinchisidan (yoki oxirgisidan) boshlab takrorlashingiz va joriy raqam kerakli raqamga mos kelishini tekshirishingiz kerak. Shunga koʻra, harakatlar soni toʻgʻridan-toʻgʻri massivdagi elementlar soniga bogʻliq. Agar bizda 100 ta raqam boʻlsa, unda keyingi elementga 100 marta oʻtishimiz va oʻyin uchun raqamni 100 marta tekshirishimiz kerak. Agar 1000 ta raqam boʻlsa, unda 1000 ta qadam tekshiriladi, bu aniq chiziqli murakkablik,