用于处理列表的所有连续子序列的朴素代码的算法复杂性：n^2 或 n^3？

algorithm time-complexity java big-o

2022-09-01 12:25:38

我正在学习测试，发现了这个问题：

我无法真正确定复杂性，我认为它要么是O（n²）要么是O（n³），我倾向于O（n³）。
有人能告诉我它是什么，为什么吗？

我的想法是O（n²）是因为在循环中，它给出了一个三角形的形状，然后循环从到，我认为这是三角形的另一半。jj = iki + 1j

public static int what(int[] arr)
{
    int m = arr[0];
    for (int i=0; i<arr.length; i++)
    {
        for (int j=i; j<arr.length;j++)
        {
            int s = arr[i];
            for (int k=i+1; k<=j; k++)
             s += arr[k];
            if (s > m)
             m = s;
        }
    }
    return m;
}

另外，如果你能告诉我它的作用？

我认为它返回数组中正整数或最大整数的加法。
但是对于像它返回的数组，我认为这是因为它有错误。如果不是，我不知道它做了什么：{99, -3, 0, 1}99

{99, 1} => returns 100
{-1, -2, -3} => return -1
{-1, 5, -2} => returns 5
{99, -3, 0, 1} => returns 99 ???

答案 1

您可以使用 Sigma 表示法有条不紊地继续操作，以获得增长复杂度的顺序：

enter image description here

答案 2

您有 3 个语句。对于大，很明显是。并且每个都有，有点短，但仍然nO(n^3)ijO(n)kO(n).

该算法返回连续项的最大总和。这就是为什么对于最后一个，它返回99，即使你有0和1，你也有-3，这将使你的总和下降到最大97。

PS：三角形意味着1 + 2 + ... + n = n(n+1) / 2 = O(n^2)