"find a peak" 算法的增长顺序是什么

Question

你好，我需要应用类似于此的算法，但问题是我需要复杂度为 O(logn)。下面代码的复杂性据说是 O(logn)，但据我了解，递归方法的增长顺序为 O(n)。所以问题是下面代码的增长顺序是什么。

  public static int findPeak(int[] array, int start, int end) {
        int index = start + (end - start) / 2;
    
        if (index - 1 >= 0 && array[index] < array[index - 1]) {
            return findPeak(array, start, index - 1);
        } else if (index + 1 <= array.length - 1 && array[index] < array[index + 1]) {
            return findPeak(array, index + 1, end);
        } else {
            return array[index];
        }
    }

Answer 1

代码的每个分支中输入数组的大小是函数中原始输入数组的一半。因此，如果 T(n) 是函数的时间复杂度，我们可以写成：

T(n) = T(n/2) + 1

1 显示分支中的比较，T(n/2) 用于任何选定的分支。因此，T(n) 在 O(log(n)).

中

Answer 2

应该是O(logn)。为简单起见（也是一种简单的思考方式），将其视为创建二叉树。在每个函数调用中，它将输入数组分成两半（在二叉树中创建节点）。所以如果输入的数量是 n 那么二叉树有 log(n) 层（一层 -> 一个函数调用）。

另请注意，在一个函数调用中，只会发生一次递归调用（要么在 if 块中，要么在 else 块中，但不能同时发生）。这可能会让您觉得 o(n) 成长。