algorithm - 一个程序的复杂度如何求最大子串的长度？

Question

我编写了一个示例 javascript 程序来查找给定字符串的最大子字符串的长度并且它有效。我无法计算它的时间复杂度。有人能帮我吗？我确实理解具有两个循环的程序是二次复杂度，具有三个循环的程序具有三次复杂度等等。这总是真的吗？这个程序有两个循环。我能说它的复杂度是O(n^2)吗？

function AllSubStrings()
{
    var myString = prompt("Enter the string");
    var arr = myString.split("");
    var tempArr = [];
    var maxLength = 0;

    for(var i = 0; i<arr.length; i++)
    {
        temp = null;

        for(var j = i; j<arr.length; j++)
        {
            if(j === i)
            {
                tempArr.push(arr[j])
                temp = arr[j];
            }
            else
            {
                temp = temp + arr[j];
                if(temp.length > maxLength)
                {
                    maxLength = temp.length;
                }
                tempArr.push(temp);
            }
        }
    }
    document.write("All SubStrings are: "+tempArr+"<br/>");
    document.write("Length of the largest substring is: "+maxLength);
}

Answer 1

您有两个 n 阶嵌套循环(其中 n 是字符串的长度)，O(n*n) = O(n²) 也是如此。

还有一些其他操作在计算大 O 时并不重要，例如 Split，需要 O(n)，但与 O(n²) 相比并不重要，或者 push 和 pop， ...在每个 for 循环中花费 O(1)，但如果我们有多个 O(1) 操作，这并不重要。

详细说明:我们知道第一个循环运行了n次，但是关于第二个循环，它将运行O(n-i)次，所以总运行时间是:

Σ(n-i) = Σ n - Σ i = n² - n(n-1)/2 = O(n^2)。