Big-O 中函数的时间复杂度

Question

我试图找出这个函数的时间复杂度：

int bin_search(int a[], int n, int x); // Binary search on an array with size n.

int f(int a[], int n) {
    int i = 1, x = 1;
    while (i < n) {
        if (bin_search(a, i, x) >= 0) {
            return x;
        }
        i *= 2;
        x *= 2;
    }
    return 0;
}

答案是 (log n)^2。怎么会？
我能得到的最好的是 log n。首先i是1，所以while会是运行log n次。
第一次交互，当i=1时，二分查找将只有一次交互，因为数组的大小为 1(i)。然后，当 i=2 时，进行两次互动，以此类推，直至达到 log n 次互动。
所以我认为适合的公式是 this。
求和是暂时的，内部等式是因为 i=1 是 log(1)，i=2 是 log(2) 等等，直到 [=22] =] 最后。

我哪里错了？

Answer 1

每次迭代对数组的前 2^i 个元素执行二进制搜索。

您可以计算操作次数（比较）：

log2(1) + log2(2) + log2(4) + ... + log2(2^m)

log(2^n)等于n，所以这个数列简化为：

0 + 1 + 2 + ... + m

其中 m 是 floor(log2(n))。

该系列的计算结果为 m * (m + 1) / 2，替换 m 我们得到

floor(log2(n)) * (floor(log2(n)) + 1) / 2

->  0.5 * floor(log2(n))^2 + 0.5 * floor(log2(n))

第一个元素支配第二个元素，因此复杂度为O(log(n)^2)

Big-O 中函数的时间复杂度

Time complexity of a function in Big-O

c

big-o

time-complexity