java - Big O 表示法的复杂性

Question

我一直在做一些问题，但没有提供答案，所以我想知道我的答案是否正确

a) 假设 a[i....j] 是一个包含 n 个元素的整数数组，x 是一个整数

int front, back;

while(i <= j) {

    front = (i + j) / 3; 
    back = 2 * (i + j) / 3;

    if(a[front] == x)
        return front;
    if (a[back] ==x)
        return back;

    if(x < a[front])
        j = front - 1;
    else if(x > a[back])
        i = back+1;
    else {
        j = back-1;
        i = front + 1;
    }
}

我的答案是 O(1)，但我感觉我错了。

B)

public static void whatIs(int n) {
    if (n > 0)
        System.out.print(n+" "+whatIs(n/2)+" "+whatIs(n/2));
}

ans:我不确定是 log4n 还是 logn，因为递归发生了两次。

Answer 1

A) 是的。 O(1) 是错误的。您将循环多次，具体取决于 i、j、x ...以及数组的内容。计算出在最好和最坏情况下循环了多少次。

B) 使用 log(a*b) -> log(a) + log(b) 简化 log(4*n)(基础高中数学)，然后应用大 O 的定义。

但这也不是正确的答案。再次，您应该回到首要原则，并计算对于给定参数 n 值调用该方法的次数。并通过归纳法进行证明。