时间戳

首页 > 解决方案 > “找峰”算法的增长顺序是什么

java - “找峰”算法的增长顺序是什么

问题描述

您好，我需要应用与此类似的算法，但问题是我需要复杂度为 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];
        }
    }

标签： javaalgorithmtime-complexitydivide-and-conquer

解决方案

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

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

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

推荐阅读