java - 使用步数计算算法的复杂性

Question

首先 - 是的，我在这里阅读了几篇关于 SO 的文章，以及其他关于估计算法复杂性的文章。

我已阅读 this , this和 this , 以及其他

我想尝试使用我编写的算法来找到最大的矩形，看看我是否完全理解我所阅读的内容。

public static long getLargestRectangle(long[] arr, int index, long max) {
    int count = 1;      //1 step * 1                               
    int i = index - 1;   //1 step * 1
    int j = index + 1;  //1 step * 1

    if(index == arr.length-1) return max; //1 step * 2

    while(i > -1 && arr[index] <= arr[i]) { //1 step * (N+1)
        count++;                             //1 step * N
        i--;                                 //1 step * N
    }
    while(j <= arr.length-1 && arr[index] <= arr[j]) { //1 step * (N+1)
        count++;                                        //1 step * N
        j++;                                            //1 step * N
    }

    max = (max < (arr[index] * count) ? (arr[index] * count) : max); //1 step * 7

    return getLargestRectangle(arr, index + 1, max); //1 step * 1
}

    //total number of steps: 1 + 1 + 1 + (N + 1) + N + N + (N + 1) + N + N + 7 
    //=> 6N + 12 = O(N) ?   

我离这里很远吗？我想要一些见解。

编辑

像这样？

T(n) = O(N) + T(n+1)
T(n) = O(N) + O(N) + T(n+2)
T(n) = O(N) + O(N) + O(N) + T(n+3)
T(n) = i * O(N) + (n+i)
T(n) = n * O(N) + (n+n)
= O(N^2)

如果这是错误的，如果您能更新您的答案并展示给我，我将不胜感激。

Answer 1

Am I way off here? I'd love some insight.

恐怕是:(

return getLargestRectangle(arr, index + 1, max); //1 step * 1

这不是第一步，它是方法的递归调用。这个方法将数组“缩小”了 1 个元素，所以这一步实际上花费了 T(n-1) , 其中T(.)是算法的时间复杂度。
结合你已有的，你得到

T(n) = T(n-1) + O(N) 

解决这个递归公式会给你算法的复杂性。

备注:T(n) = T(n-1) + O(N)是合成糖，其实应该是T(n) <= T(n-1) + CONST*N对于一些常量 CONST ，因为您不能将集合 ( O(N)) 添加到标量 (T(n-1))。

另请注意:N!=n . n随时间变化，N是数组的初始长度。之所以如此，是因为你的算法实际上是从n遍历的。 ( index ) 到 0，然后从 n至 N .
但是，这不会改变大 O 表示法的时间复杂度。