就 Big O 而言，给定函数的时间复杂度应该是多少？

Question

int find_peak (int n, int A []) {
    int left, right, lmid, rmid;
    left = 0;
    right = n - 1;
    while (left + 3 <= right) {
        lmid = (2 * left + right) / 3;
        rmid = (left + 2 * right) / 3;
        if (A[lmid] <= A[rmid])
            left = lmid;
        else
            right = rmid;
    }
    int x = left;
    for (int i = left + 1; i <= right; i ++)
        if (A[i] > A[x])
            x = i;
    return A[x];
}

我试图解决这个函数的 BigO 符号，但我对此很困惑。是 O(log n) 还是其他？我可以在脑海中稍微解决它，但我不能正确地解决它。

Answer 1

是的，循环在每次迭代时大致减半

lmid = (2 * left + right) / 3;
rmid = (left + 2 * right) / 3;
if (A[lmid] <= A[rmid])
    left = lmid;
else
    right = rmid;

准确的说是log_1.5(n)，因为实际长度right-left只减少了¹/₃，而不是将迭代减半。复杂度仍然是 O(log(n))

你可以在这里试试https://onlinegdb.com/rkI5gn3Xd

感谢 chqrlie 提示我给出更详细的答案

Answer 2

上面代码的复杂度应该是O(log3n) 即...logn base 3。因为在 while 循环 中，rmid 的值总是大于 lmid。因此，对于给定的右值，即...n, left的值会在每次迭代时减少1/3的倍数

就 Big O 而言，给定函数的时间复杂度应该是多少？

What should be the time complexity of the given function in terms of Big O?

c

time-complexity

big-o

complexity-theory