Find() 函数的复杂度是多少

Question

我有两个版本的 find 函数，这两个版本都在数组中搜索一个整数值，return 它的位置（如果存在）。在最坏的情况下，函数 find1() 将搜索多达 N 个元素，另一方面，find2() 函数将搜索多达 N/2 最坏情况下的元素。这是否意味着 find2() 函数复杂度降低为 O(N/2)?

我假设数组 arr 包含非重复值。

函数：find1()

int find1(int value){
    for (int i = 0; i < N; i++){
        if (arr[i] == value){
            return i;
        }
    }
    return -1;
}

函数：find2()

int find2(int value){
    for (int i = 0, j = N - 1; i <= j; i++, j--){
        if (arr[i] == value){
            return i;
        }
        if (arr[j] == value){
            return j;
        }
    }
    return -1;
}

Answer 1

首先，第一个版本在最坏的情况下执行 n 次迭代，并且在每次迭代中执行固定数量的操作。第二个版本在最坏的情况下执行 n / 2 次迭代，并且在每次迭代中，也执行恒定数量的操作，但常数更大。因此，没有理由认为第一个是 O(n) 而第二个是 O(n / 2).

无论如何，O(n) = O(n / 2)。由definition of O,O(n)表示有常数c₁这样对于每个 n > n₁,

f(n) < c₁ n.

同理，O(n / 2)表示存在常数c₂ 这样对于每个 n > n₂,

f(n) < c₂ n / 2 = (c₂ / 2) n.

因为对于任何 n > max(n₁, n₂) 不等式c₁ = c₂ / 2 成立，这两者中的每一个都暗示着另一个。