10-amaliy ishi. ”Ajrat va hukmronlik qil” prinsipi buyicha ishlaydigan algoritmlarni loyihalash

ac
𝑅
2
+ (𝑎𝑑 + 𝑏𝑐)𝑅 + 𝑏𝑑
 
Shunday qilib, n-raqamli sonlarning ko'payishi n-raqamli sonlarni 
ko'paytirishning to'rtta vazifasi va keyinchalik bit siljishi va natijalarni qo'shish 
bilan qisqartirildi. Qabul qilingan protseduraning ish vaqti 
𝑂(𝑛
2
)
tomonidan 
baholanishi mumkin. 
Hozircha bu yondashuv ish vaqtida g'alaba qozonmaydi, ammo Karatsuba aslida 
faqat uchta ko'payish-raqamli raqamlar etarli ekanligini payqadi 
(𝑎𝑑 + 𝑏𝑐) = (𝑎 + 𝑏)(𝑐 + 𝑑) − 𝑎𝑐 − 𝑏𝑑
Shunday qilib, x×y ning barcha asarlari qo'shimcha, olib tashlash va bit 
kesish lineer operatsiyalari bilan amalga oshirilishi mumkin va umumiy ish vaqti
𝑂(𝑛
𝑙𝑜𝑔3
)
deb baholanadi.
Natijada, bu bizni x×y ishining natijasiga olib boradi. 
Karatsuba Algoritmi 
1 qadam: a × C = 56 × 12 mahsulotini hisoblang, bu 672. 
2 bosqichi: B × D = 78 × 34 = 2652 ni hisoblang. 
Keyingi ikki qadam ham tushunarsiz. 
3 qadam: hisoblash (a + b) × (C + d) = 134 x 46 = 6164. 

---

4-qadam: uchinchi qadam natijasida birinchi ikki qadam natijalarini ayirsak: 6164-
672-2652 = 2840. 
Nihoyat, biz 1, 2 va 4 bosqichlarining natijalarini umumlashtiramiz, lekin faqat 1 
bosqichida javob berish uchun to'rtta oxirgi nol qo'shilgandan so'ng va 4 
bosqichida javob berish uchun ikkita oxirgi nol. 
5-Qadam: Hisoblash 
672 × 104 + 2840 × 102 + 2652 =
= 6 720 000 + 284 000 + 2652 = 70 066552.
 
Shakl 1. Ikki raqamning ishini hisoblash vaqti 
Birlashish tartibida 
Int a [maxn] ning ba'zi tartibsiz qatorlari berilsin. Asosiy g'oya shundaki, har bir 
qadamda biz qatorni 2 teng qismlarga ajratamiz, ularni tartiblaymiz va keyin ikkita 
tartiblangan qismni birlashtiramiz. Ya'ni, recursive saralash olinadi, chunki bu 2 
qismlarining har biri xuddi shunday tartiblanadi. Rekursiyadan chiqish 3 
elementdan kamroq bo'lsa, sodir bo'ladi. Agar ular faqat 2 bo'lsa, biz ularni kerakli 
darajada o'zgartiramiz. Agar faqat 1 elementi qolsa, uni yolg'iz qoldiring. 
Misol. 7 ta elementning asl qatori berilsin: 7 4 2 1 0 5 3 
Qadam 0: 7 4 2 1 0 5 3 
1 bosqichi: 4 7 2 1 0 5 3 
2-bosqich: 4 7 1 2 0 5 3 

---

3 qadam: 1 2 4 7 0 5 3 
Barcha huquqlar himoyalangan 
5-qadam: 0 1 2 3 4 5 7 
Har bir qadamni batafsil ko'rib chiqing. 
Step1: birinchidan, recursion iloji boricha chuqur, ya'ni a[0] va a[1] elementlariga 
tushadi. 7 > 4dan beri ular joylarni almashtiradilar. 
2 bosqichi: keyin a[3] va a[4] elementlariga qarang. Ular ham noto'g'ri ekan, ularni 
joylarda o'zgartiramiz. 
3 qadam: endi 0 va 3 indekslari bo'lgan elementlar haddan tashqari. Bizda 2 ta 
tartiblangan qismlar mavjud. Ularni[0] dan a[3] ga ajratish uchun ularni 
birlashtirish kerak. Buning uchun biz chap va o'ng tomondan minimal elementni 
yozadigan qo'shimcha buf qatorini boshlaymiz. Ular allaqachon tartiblangan ekan, 
biz chap elementlarni solishtiramiz. 1 < 4 dan boshlab, 1 bufga boradi. Bundan 
tashqari, xuddi shu sabablarga ko'ra, 2 bufga yuboriladi. Elementlar o'ng tomonda 
tugaganligi sababli, 4 va 7 elementlari bufga yuboriladi. Endi buf hosil bo'lganda, 
uning tarkibini a qatoriga qo'ying. 
Qadam 4: xuddi shunday, biz o'ng qismi bilan, ya'ni.qator bir parcha va 4 6 dan 
indekslar bilan. 
5 bosqichi: chap va o'ng qismlarni birlashtirish. Tartiblangan qatorni olamiz. 
Va yana ravshanlik uchun rasm: 

---

Код: 
#include

#include

using
namespace
std
; 
#define
maxn
100
int
a[
maxn
]; 
int
n; 
void
merge(
int
l,
int
r) 
{
if
(r
==
l) 
return
; 
if
(r
-
l
==
1
)
{ 
if
(a[r]
<
a[l]) 
swap(a[r],
a[l]); 
return
; 
} 
int
m
=
(r
+
l)
/
2
; 
merge(l,
m); 
merge(m
+
1
,
r); 
int
buf[
maxn
]; 
int
xl
=
l; 
int
xr
=
m
+
1
; 
int
cur
=
0
; 
while
(r
-
l
+
1
!=
cur)
{ 
if
(xl
>
m) 
buf[cur++]
=
a[xr++]; 
else
if
(xr
>
r) 
buf[cur++]
=
a[xl++]; 
else
if
(a[xl]
>
a[xr]) 
buf[cur++]
=
a[xr++]; 
else
buf[cur++]
=
a[xl++]; 
} 
for
(
int
i
=
0
;
i
<
cur;
i++) 
a[i
+
l]
=
buf[i]; 
} 
int
main()
{ 
cin
>>
n; 
for
(
int
i
=
0
;
i
<
n;
i++) 
cin
>>
a[i]; 
merge(
0
,
n
-
1
); 
for
(
int
i
=
0
;
i
<
n;
i++) 
cout
<<
a[i]
<<
"
"
; 
getch(); 
return
0
; 
} 
Сортировка слиянием - это довольно быстрая сортировка, время работы которой 
О(n * log n). Однако ее недостатком является тот факт, что она требует относительно 
много памяти.