为什么最大和子数组的蛮力是O(n^2)？

Question

null

在一个视频教程中，作者提到暴力方法是O(n^2)，阅读另一个答案，一个人认为是O(n^2)，另一个人认为是O(n^3)

强力是O(n^2)还是O(n^3)？更重要的是，您能说明您对蛮力方法执行了哪些分析以知道它是o（？）吗？

Answer 1

嗯，这取决于力量有多大。

如果我们生成所有(i,j):i<=j对并计算它们之间的和，则为O(n^3):

....
for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++) {
        int sum = 0;
        for (int k = i; k <= j; k++)
            sum += a[k];
        if (sum > max)
            max = sum;
    }

如果我们从所有位置开始并计算运行和，它是O(n^2):

....
for(int i = 0; i < n; i++) {
    int sum = 0;
    for (int j = i; j < n; j++) {
        sum += a[j];
        if (sum > max)
            max = sum;
    }
}