Vaqt murakkabligi
Eng yaxshi: O(log n)
O'rtacha: O(log n)
Eng yomon: O(log n)
Ikkilik darajaga oshirish algoritmi aⁿ qiymatini O(log n) vaqtda hisoblaydi. Buning uchun a ni n marta o'ziga ko'paytirish o'rniga, har bir qadamda daraja ko'rsatkichi ikkiga bo'linadi.
Qanday ishlaydi:
1. Asosiy holat: a⁰ = 1
2. Rekursiv ravishda half = binPow(base, floor(exp / 2)) qiymatini hisoblaymiz
3. Agar exp juft bo'lsa, half × half qiymatini qaytaramiz
4. Agar exp toq bo'lsa, half × half × base qiymatini qaytaramiz
Nima uchun tez:
Har bir rekursiv chaqiruv daraja ko'rsatkichini ikkiga bo'ladi. Shu sababli rekursiya chuqurligi n ga emas, log₂ n ga mutanosib bo'ladi.
Vaqt murakkabligi:
Eng yaxshi holat: O(log n)
O'rtacha holat: O(log n)
Eng yomon holat: O(log n)
Xotira murakkabligi: Rekursiv chaqiruvlar steki uchun O(log n)
Qo'llanilishi:
- Kriptografiyada modulli darajaga oshirish
- Matritsalarni tez darajaga oshirish
- Musobaqaviy dasturlash va sonlar nazariyasi
Asosiy g'oya — darajalarni qayta ishlatish: a^(n/2) qiymatini bilganingizdan so'ng, uni kvadratga oshirib, hisoblashning katta qismini darhol bajarishingiz mumkin.
O'xshash algoritmlar
Ko'p beriladigan savollar
- Ikkilik darajaga oshirish nima?
- Ikkilik darajaga oshirish algoritmi aⁿ qiymatini O(log n) vaqtda hisoblaydi. Buning uchun a ni n marta o'ziga ko'paytirish o'rniga, har bir qadamda daraja ko'rsatkichi ikkiga bo'linadi.
- Ikkilik darajaga oshirish murakkabligi qanday?
- Vaqt (o'rtacha): O(log n) · Xotira: O(log n)
- Ushbu Ikkilik darajaga oshirish vizualizatori kimlar uchun?
- Ikkilik darajaga oshirish vizualizatsiyasi "Bo‘lib tashla va hukmronlik qil" kategoriyasida o'rta darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Ikkilik darajaga oshirish ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Bo‘lib tashla va hukmronlik qil) quyidagilarni ko'rishingiz mumkin: Tower of Hanoi. Har biri interaktiv vizualizatsiyaga ega.