1

我编写了一个示例 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);
}
4

3 回答 3

1

由于您有两个 N 阶循环，因此复杂度为 O(N2)。

于 2013-06-09T10:37:45.813 回答
1

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

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

详细说明：我们知道第一个循环运行n时间，但是关于第二个循环，它将运行 O(ni) 时间，因此总运行时间为：

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

于 2013-06-09T10:28:20.887 回答
0

简单的答案：由于您有两个嵌套循环，每个循环都按 n 的顺序运行，因此总运行时间为 O(n*n)。

更详细一点：第一个循环从 0 运行到 n-1，第二个循环从 i 运行到 n-1。所以对于每个 i 内部循环运行 n+n-1+n-2+...1 = n*(n+1)/2= O(n*n)

于 2013-07-17T19:35:03.477 回答