Mustaqil ishi topshirgan: qabullagan: reja

Butun sonlarni ko‘paytirish
Ushbu ko'paytirish algoritmi ba'zan rus yoki dehqon deb ataladi, garchi u Qadimgi Misrda ham ma'lum bo'lgan.
Birinchi omil ketma-ket ikkiga ko'paytiriladi, ikkinchisi esa to'liq 2 ga bo'linadi. Natijalar ikkinchisi 1 bo'lguncha ikkita ustunga yoziladi.
Ko'paytirish natijasi birinchi ustundagi raqamlarning yig'indisi, ikkinchi ustundagi toq raqamlarning qarama-qarshiligi.
Butun sonlarni bo'lish va 2 ga ko'paytirishni siljish yo'li bilan bajarish mumkin bo'lganligi sababli, bu algoritm \ (2 \ log_2 n \) siljish amallarini beradi, bu erda \ (n \) ikkita sondan kichikroqdir. Eng yomon holatda, \ (\ log_2 n - 1 \) qo'shish operatsiyalari ham olinadi. Qanday bo'lmasin, vaqtning murakkabligi \ (T (n) = \ matematik (O) (\ log n) \).
Algoritmni samarali amalga oshirish uchun qo'shimcha xotira deyarli talab qilinmaydi va u kiritilgan ma'lumotlarga bog'liq emas, shuning uchun \ (S (n) = \ mathcal (O) (1) \)
Yana shuni ta'kidlash kerakki, yanada samarali algoritmlar mavjud. Biroq, \ (\ mathcal (O) (n) \) qo'shish operatsiyalarini talab qiladigan "sodda" amalga oshirish bilan solishtirganda, bu algoritm nisbatan samaralidir.
Misol
23 ni 43 ga ko'paytiring.
Ikkinchi omil sifatida 23 ni olaylik.

43	23	g'alati
86	11	g'alati
172	5	g'alati
344	2
688	1	g'alati

Natija \ (43 + 86 + 172 + 688 = 989 \)
Bizda 10 ta smenali operatsiya va 4 ta qo'shimcha operatsiya mavjud. Malumot uchun, \ (\ log_2 (23) \ taxminan 4,52 \).
Algoritmning murakkabligini aniqlash
Asimptotik tahlilda olingan murakkablik funksiyasining bahosi algoritmning murakkabligi deyiladi.
Shuni yodda tutish kerakki, algoritmning murakkabligi bo'yicha bir nechta taxminlar mavjud.
Murakkablik funktsiyasining asimptotik xatti-harakati operatsion murakkablikdir. Unga qo'shimcha ravishda siz quyidagi qiyinchiliklar turlarini belgilashingiz mumkin.
Vaqtinchalik murakkablik - uzunlikdagi kirish ma'lumotlari bo'yicha algoritmning ishlash vaqtining asimptotik bahosi P. Shubhasiz, hisoblash protseduralarini parallellashtirish mavjud bo'lmaganda, algoritmning ishlash vaqti bajarilgan operatsiyalar soni bilan yagona aniqlanadi. Operatsiyalarning davomiyligini ifodalovchi doimiy koeffitsientlar vaqt murakkabligi tartibiga ta'sir qilmaydi, shuning uchun operatsion va vaqt murakkabligi uchun formulalar ko'pincha bir-biriga to'g'ri keladi.
Kapasitiv murakkablik - uzunlikdagi kirish ma'lumotlari bo'yicha algoritmni bajarishda bir vaqtning o'zida mavjud bo'lgan skalerlar sonining asimptotik bahosi P.
Strukturaviy murakkablik - algoritmdagi boshqaruv tuzilmalari sonining xarakteristikasi va ularning interpozitsiyasining o'ziga xosligi.
Kognitiv murakkablik - amaliy sohalardagi mutaxassislar tomonidan tushunish uchun algoritm mavjudligining xarakteristikasi.
Asimptotiklarning turlari va belgilanishi
Algoritmlarning asimptotik tahlilida matematik asimptotik tahlilning yozuvidan foydalanish odatiy holdir. Bunday holda, algoritmlarning murakkabligining uchta bahosi (asimptotikasi) ko'rib chiqiladi, ular quyidagicha belgilanadi:

• 
  1) / (i) = O ^ (n))- murakkablik funksiyasining asimptotik aniq bahosi / («), yoki algoritmning operatsion murakkabligi;
  
• 
  2) /(n) = 0 (§ (n)) - murakkablik funktsiyasi uchun asimptotik keskin yuqori chegara / ( P);
  
• 
  3) / (n) =? 2 (# (n)) murakkablik funksiyasi uchun asimptotik aniq past bahodir / ( P).
  

Belgilash o'rniga C1 ^ (n)) juda tez-tez "o" harfi bilan oddiyroq o (^ (")) kichik kursivda ishlatiladi.
Formulalarning semantikasini misol orqali tushuntirib beraylik: agar u / (i) = 0 (^ 2 (l)) deb yozilsa, BU funksiyani bildiradi. g (n) = og2 (n) murakkablik funksiyasi uchun asimptotik aniq bahodir / (a). Aslida, bayonot shaklida ikki pozitsiyali ta'rif mavjud: