Darajaga ko‘tarish (pow)
Kalkulyatorda 2 sonini 30-darajaga ko‘tarishni so‘rasangiz, natija bir soniyada chiqadi. Lekin buni qanday hisoblash mumkin? Eng sodda yo‘l — 2 ni o‘ziga 30 marta ko‘paytirish. Bu ishlaydi, lekin daraja katta bo‘lgani sari — masalan, 2^1000000 — bu yondashuv juda ko‘p vaqt oladi. Bu masala rekursiyani ikki xil tarzda qo‘llash mumkinligini, va ikkalasining murakkabligi qanchalik farq qilishini ko‘rsatish uchun juda qulay.
Masala
x sonini n-darajaga ko‘tarish natijasini, ya’ni x^n ni hisoblang. n manfiy bo‘lmagan butun son deb qabul qilinadi.
Sodda rekursiv yechim
Darajaga ko‘tarishning ta’rifini eslaylik: x^n — bu x ni o‘ziga n marta ko‘paytirish. Buni rekursiv shaklda yozish mumkin:
Tayanch holat — n = 0 bo‘lganda, chunki har qanday son nolinchi darajada 1 ga teng.
Bu yechim to‘g‘ri natija beradi, lekin uning ichida nima sodir bo‘layotganini ko‘rish uchun POW(2, 4) ni dry run qilaylik.
POW(2, 4)
= 2 * POW(2, 3)
= 2 * (2 * POW(2, 2))
= 2 * (2 * (2 * POW(2, 1)))
= 2 * (2 * (2 * (2 * POW(2, 0))))
= 2 * (2 * (2 * (2 * 1)))
= 16
Har chaqiruv nni bittaga kamaytiradi, shuning uchun n marta chaqiruv bo‘ladi. Call stackda bir vaqtning o‘zida n + 1 ta freym turadi:
+------------------+
| POW(2, 0) = 1 | ← eng ichki freym
+------------------+
| POW(2, 1) |
+------------------+
| POW(2, 2) |
+------------------+
| POW(2, 3) |
+------------------+
| POW(2, 4) | ← boshlang‘ich chaqiruv
+------------------+
Bu yechimning vaqt murakkabligi O(n), xotira murakkabligi ham O(n) — chunki call stack chuqurligi nga proportsional. n kichik bo‘lganda bu yetarli, lekin n = 1 000 000 bo‘lganda bu variant ham sekin ishlaydi, ham stack overflowga yaqinlashadi.
Tezroq yechim: darajani yarmiga bo‘lish
Muammoni boshqacha ko‘raylik. x^8 ni hisoblash uchun xni sakkiz marta ko‘paytirish shart emas. Buning o‘rniga:
Har bosqichda daraja ikki barobar kamayadi, bir martalik ko‘paytirish o‘rniga. Bu g‘oya kvadratga ko‘tarish orqali tez darajaga ko‘tarish (exponentiation by squaring) deb ataladi.
Juft va toq darajalar uchun qoida biroz farq qiladi:
Toq daraja uchun qo‘shimcha x ko‘paytirish kerak, chunki n/2 butun bo‘linishda qoldiq tashlanib ketadi.
FUNCTION FAST_POW(x, n)
IF n = 0
RETURN 1
yarim = FAST_POW(x, n / 2) // butun bo‘lish
IF n juft
RETURN yarim * yarim
RETURN x * yarim * yarim
yarim natijasini alohida saqlash muhim — aks holda FAST_POW(x, n / 2)ni ikki marta chaqirish kerak bo‘lib qoladi, bu esa butun optimizatsiyani yo‘qqa chiqaradi.
Bosqichma-bosqich tahlil
FAST_POW(2, 10) ni dry run qilaylik.
FAST_POW(2, 10) 10 juft
yarim = FAST_POW(2, 5)
FAST_POW(2, 5) 5 toq
yarim = FAST_POW(2, 2)
FAST_POW(2, 2) 2 juft
yarim = FAST_POW(2, 1)
FAST_POW(2, 1) 1 toq
yarim = FAST_POW(2, 0)
FAST_POW(2, 0) = 1 ← tayanch holat
RETURN 2 * 1 * 1 = 2
RETURN 2 * 2 = 4
RETURN 2 * 4 * 4 = 32
RETURN 32 * 32 = 1024
Natija — 1024, xuddi 2^10 kabi. Diqqat qiling: sodda yechimda 10 ta chaqiruv kerak bo‘lsa, bu yerda atigi 4 ta chaqiruv bilan yetarli bo‘ldi.
Nima uchun bu tezroq?
Sodda yechimda har chaqiruv nni bittaga kamaytiradi — bu daraxtni chiziqli ravishda pastga tushiradi. Tez yechimda esa har chaqiruv nni yarmiga kamaytiradi:
Bu formula bizga tanish — Rekursiya mavzusida binary search uchun ko‘rgan edik. n sonini nechta marta ikkiga bo‘lganda 1ga tushishi — bu log₂n. Demak, chaqiruvlar soni, ya’ni vaqt murakkabligi O(log n).
Xotira murakkabligi ham O(log n), chunki call stack chuqurligi chaqiruvlar sonига teng.
Murakkablik taqqoslash
| Yondashuv | Vaqt | Xotira | Sabab |
|---|---|---|---|
Sodda rekursiya (x * POW(x, n-1)) |
O(n) |
O(n) |
Har chaqiruv nni 1ga kamaytiradi |
Kvadratga ko‘tarish (FAST_POW) |
O(log n) |
O(log n) |
Har chaqiruv nni yarmiga kamaytiradi |
n = 1 000 000 uchun sodda yechim million marta chaqiruv qiladi, tez yechim esa atigi ~20 marta. Farq bir necha ming barobar bo‘lishi mumkin — bu O(n) va O(log n) orasidagi farqning amaliy ta’siri qanchalik katta bo‘lishini ko‘rsatadi.
Edge case’lar
n = 0
Har qanday x uchun x^0 = 1, hatto x = 0 bo‘lsa ham (matematik konventsiyaga ko‘ra 0^0 odatda 1 deb qabul qilinadi). Tayanch holat bu holatni to‘g‘ridan-to‘g‘ri qamrab oladi.
x = 0, n > 0
0^n = 0 bo‘lishi kerak. Algoritm buni to‘g‘ri hisoblaydi, chunki 0 ni istalgan marta o‘ziga ko‘paytirsa ham natija 0 bo‘lib qoladi — alohida shart yozish shart emas.
Manfiy daraja
Yuqoridagi ikkala algoritm ham n manfiy bo‘lmagan deb faraz qiladi. Agar manfiy darajalarni ham qo‘llab-quvvatlash kerak bo‘lsa (x^(-n) = 1 / x^n), buni alohida holat sifatida boshida tekshirish kerak:
Bu yerda x = 0 va n < 0 holati alohida diqqat talab qiladi, chunki nolga bo‘lish mumkin emas.
Katta natijalarda overflow
Daraja katta va x bittadan katta bo‘lsa, natija juda tez o‘sadi. 2^100 kabi qiymatlar oddiy butun son turiga sig‘masligi mumkin. Bu rekursiya xatosi emas — ishlatilayotgan son turining chegarasi bilan bog‘liq muammo, lekin katta darajalar bilan ishlaganda buni hisobga olish kerak.
Real qo‘llanish: modulli darajaga ko‘tarish
Kriptografiyada (masalan, RSA algoritmida) juda katta sonlarni juda katta darajaga ko‘tarish va natijani biror modul bo‘yicha qoldig‘ini olish kerak bo‘ladi: x^n mod m. To‘g‘ridan-to‘g‘ri x^n ni hisoblab, keyin mod m olish amalda mumkin emas — natija shu qadar katta bo‘ladiki, uni xotirada saqlashning o‘zi muammo bo‘ladi.
Yechim — har bir ko‘paytirishdan keyin darhol mod m olish:
FUNCTION FAST_POW_MOD(x, n, m)
IF n = 0
RETURN 1 mod m
yarim = FAST_POW_MOD(x, n / 2, m)
natija = (yarim * yarim) mod m
IF n toq
natija = (natija * x) mod m
RETURN natija
Bu texnika aynan shu O(log n) g‘oyasiga tayanadi, lekin sonlarning hech qachon nazoratsiz kattalashib ketmasligini ta’minlaydi.
Eng muhim xulosa
Bir xil matematik masala ikki xil rekursiv strukturaga ega bo‘lishi mumkin, va bu struktura tanlovi vaqt murakkabligini butunlay o‘zgartiradi. x * POW(x, n-1) shaklidagi rekursiya muammoni bittadan kamaytiradi va O(n) beradi; nni yarmiga bo‘lish esa O(log n) beradi. Rekursiv yechim yozishda “muammo har safar qanchaga kichrayadi?” degan savolga javob berish — algoritmning tezligini belgilaydigan asosiy omillardan biri.
Keyingi masalada rekursiya yordamida ikkita allaqachon saralangan massivni bitta saralangan massivga birlashtirishni ko‘rib chiqamiz — bu Merge sort algoritmining yuragi bo‘lgan operatsiya.