离散对数算法

我经常看到离散对数是个难题。但是，我不太明白这可能是怎么回事。在我看来，普通的二进制搜索可以很好地满足这个目的。例如，离散对数算法

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

离散对数算法

回答

相关问题