ALGO查找功率即n^P

的算法查找Ñ^ P是：ALGO查找功率即n^P

unsigned long long power(unsigned n, unsigned p) 
{ 
    unsigned long long x=1, y=n; 
    while(p > 0) 
    { 
     if(p&1) x *= y; 
     y *= y; 
     p >>= 1; 
    } 
    return x; 
}

有人可以解釋該算法背後的邏輯/數學。我知道它的工作原理和一些測試案例（空運行）。我的意思是它是如何工作的，以及如何從一般的樸素方法中獲得高效。

來源

2012-12-24 gopi1410

這是O（log n）與樸素方法的O（n）相比。它將在每次迭代中將指數減半。 – nhahtdh

IITian問一個問題，那麼它一定很難：p –

爲什麼不每次迭代printf x，y＆p？這很容易幫助你理解。這段代碼基本上可以找到遍歷p的各個位，而不是運行i = 0到p的循環。 – anishsane

這是exponentiation by squaring：>>= 1是編寫/= 2的一種奇特方式。

背後的想法是，如果p是偶數，你可以採取n^(p/2)並將其平方;當p爲奇數時，p-1必須是偶數，所以你可以取其平方值n^((p-1)/2)，然後將結果乘以n以補償在平方之前從p減去的1。

來源

2012-12-24 14:29:14 dasblinkenlight

是的，我知道它的'/ = 2'和那個'（p＆1）'檢查它是否奇數，但我想知道它背後的邏輯及其複雜度 – gopi1410

感謝鏈接btw，通過它 – gopi1410

啊，謝謝說明！得到它了：） – gopi1410

ALGO查找功率即n^P

回答

相關問題