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

Question

我正在研究测试并发现了这个问题:

我无法确定复杂性,我认为它是O(n ²)或O(n ³)而我倾向于O(n ³).
有人能告诉我它是什么以及为什么？

我认为它是O(n ²)是因为在j循环中,j = i它给出了一个三角形的形状,然后k循环从i + 1到j,我认为是三角形的另一半.

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 ???

Answer 1

您可以使用Sigma Notation有条不紊地处理增长复杂性的顺序:

Answer 2

你有3个声明.对于大型n,很明显是O(n^3).i并j有O(n)各自k是短一点点,但仍O(n).

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

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

Answer 3

码:

for (int i=0; i<arr.length; i++) // Loop A
{
    for (int j=i; j<arr.length;j++) // Loop B
    {
        for (int k=i+1; k<=j; k++) // Loop C
        {
            // ..
        }
    }
}

Big-O的渐近分析:

Loop A: Time = 1 + 1 + 1 + .. 1 (n times) = n

Loop B+C: Time = 1 + 2 + 3 + .. + m = m(m+1)/2

Time = SUM { m(m+1)/2 | m in (n,0] }

Time < n * (n(n+1)/2) = 1/2 n^2 * (n+1) = 1/2 n^3 + 1/2 n^2

Time ~ O(n^3)