Pemangkatan dengan Pengkuadratan

To the point aja,ya?
Terkadang, dalam pemrograman diperlukan operasi pemangkatan. Hal ini dapat dilakukan dengan menggunakan looping For,seperti dalam pseudocode berikut :
for i:=2 to n do begin
pangkat->pangkat*x
end;
Kode di atas memanfaatkan konsep pangkat,yaitu perkalian x dengan x sebanyak n kali (untuk x^n).
Berapakah kompleksitasnya?O(n). Ya,program berjalan sebanyak n kali. Untuk n yang kecil mungkin masih tidak masalah, tetapi untuk n yg mencapai milyaran tentu cara ini sangat tidak efisien.
Lalu bagaimana solusinya?
Salah satu triknya ialah dengan melakukan pemangkatan dengan pengkuadratan.Berikut rumusnya :

Untuk x^n,apabila n genap,maka $x^n = (x^{n/2})^2$.
Apabila n ganjil,maka $x^n = x ( x^{\lfloor n/2 \rfloor})$.

Mungkin ada yang bilang,"Lah,sama aja dong?"
Ya iyalah sama.Kalo beda ya nanti beda hasilnya -_-.

Trik ini bisa kita implemen ke dalam fungsi rekursi,seperti pseudocode berikut :
pangkat(x,n : integer): integer
if n = 0 then return 1
else
hitung ← pangkat(x,n/2)
if n genap return hitung*hitung else
return x*hitung*hitung

Bagaimana dengan kompleksitasnya? Dengan sedikit analisa,dapat terlihat bahwa kompleksitas program ini ialah $O(\log n)$. Jauh lebih cepat,bukan? Oiya, Jangan lupa untuk menyimpan pangkat(x,n/2) dalam variabel hitung, kalau tidak maka secara kompleksitas akan tetap $O(n)$.


Btw,kalau bingung apa itu kompleksitas, coba deh googling.Itu agak panjang,jadi saya males ngetiknya :v

Sekian,
CMIIW.