離散對數算法

我經常看到離散對數是個難題。但是，我不太明白這可能是怎麼回事。在我看來，普通的二進制搜索可以很好地滿足這個目的。例如，離散對數算法

binary_search(base, left, right, target) { 
    if (pow(base, left) == target) 
     return left; 
    if (pow(base, right) == target) 
     return right; 
    if (pow(base, (left + right)/2) < target) 
     return binary_search(base, (left + right)/2, right, target); 
    else 
     return binary_search(base, left, (left + right)/2, target); 
} 

log(base, number) { 
    left = 1; 
    right = 2; 
    while(pow(base, p) < number) { 
     left = right; 
     right *= 2; 
    } 
    return binary_search(base, left, right, number); 
}

如果天真的實施只是遞增p直到pow(base, p)爲O（n），那麼可以肯定這個二進制搜索是O（日誌（N）^ 2）。

或者我不明白這個算法是如何測量的？

編輯：我通常不會編寫二進制搜索，所以如果有一些微不足道的實現錯誤，那麼請忽略它或修復中進行編輯。

來源

2011-12-17 Puppy

'pow'的複雜性是什麼？ – 2011-12-17 19:05:17

@JoshLee：最大的力量是對數。 – Puppy 2011-12-17 19:06:31

試試這個http://en.wikipedia.org/wiki/Baby-step_giant-step – kilotaras 2011-12-17 19:27:35

您的算法假定< b意味着pow（base，a）< pow（base，b）。

對於自然數，這是正確的，但它在有限循環組中不起作用（當'pow'以某個數爲模數計算時）。

來源

2011-12-17 19:11:20 Daniel

這很清楚地解釋了我的直覺和真相之間的差異 - 我沒有考慮過這個。 – Puppy 2011-12-17 19:17:59

離散對數算法

回答

相關問題