java - 将算法从 o(n) 转换为 o(1)

Question

基本上我想要的是，如果一个数字 n 可以被 b 整除 a(count) 次，然后找到 a(count)，并将n除以b a(count)次。

也就是说，

count = 0;
while(n%b == 0)
    n=n/b;
    count = count + 1;

如何优化这个，让一​​切都一步到位

Answer 1

您可以在 O(log(a)) 中通过应用二进制搜索在排序的“列表”上找到最后一个等于 1 的元素。

列表是隐喻的，其中的每个元素都是在通过简单计算查询时即时计算的:

list[i] = 1      n % a^i == 0
          0      otherwise

您可以先找到可能的 a 使用指数的范围:

curr = b
tempA = 1
while n % curr == 0:
    curr = curr  * curr
    tempA = tempA *2

然后，在范围 [tempA/2, tempA] 上运行二进制搜索。此范围的大小为 (a/2)，因此找到符号列表包含 1 的最后一个“元素” - 在 O(loga)< 中完成 乘法。

代码+演示:

private static int specialBinarySearch(int n, int b, int aLow, int aHigh) {
    if (aHigh == aLow) return aHigh;
    int mid = (aHigh - aLow)/2 + aLow;
    //pow method can be optimized to remember pre-calculated values and use them
    int curr = (int)Math.round(Math.pow(b, mid));
    if (n % curr == 0) { //2nd half, or found it:
        if (n % (curr*b) != 0) return mid; //found it
        return specialBinarySearch(n, b, mid+1, aHigh); //2nd half
    }
    else return specialBinarySearch(n, b, aLow, mid); //first half

}

public static int findA(int n, int b) { 
    int curr = b;
    int tempA = 1;
    while (n % curr == 0) {
        curr = curr  * curr;
        tempA = tempA *2;
    }
    return specialBinarySearch(n, b, tempA/2, tempA);
}
public static void main(String args[]) {
    System.out.println(findA(62,2)); //1
    System.out.println(findA(1024,2)); //10
    System.out.println(findA(1,2)); //0
    System.out.println(findA(100,2)); //2
    System.out.println(findA(6804,3)); //5

}