1

特定の文字列の最大の部分文字列の長さを見つけるためのサンプル JavaScript プログラムを作成しましたが、動作します。時間の複雑さを計算できません。誰かが私を助けることができますか？ループが 2 つあるプログラムは 2 次複雑さであり、ループが 3 つあるプログラムは 3 次複雑さなどであることは理解しています。これは常に真実ですか？このプログラムには 2 つのループがあります。その複雑さは 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 (n は文字列の長さ) の 2 つのネストされたループがあるため、O(n*n) = O(n 2 ) です。

big O の計算には重要ではない操作が他にもいくつかあります。たとえば、Split は O(n) を使用しますが、O(n 2 ) との比較は重要ではありません。 1) ですが、複数の O(1) 操作がある場合は重要ではありません。

詳細について:最初のループの実行時間はわかっていますがn、2 番目のループについては O(ni) 時間実行されるため、合計実行時間は次のようになります。

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

于 2013-06-09T10:28:20.887 に答える
0

簡単な答え: n の順序で実行される 2 つのネストされたループがあるため、合計実行時間は O(n*n) です。

もう少し詳細なもの: 最初のループは 0 から n-1 まで実行され、2 番目のループは i から n-1 まで実行されます。i ごとに、n+n-1+n-2+...1 = n*(n+1)/2= O(n*n) の内部ループが実行されます。

于 2013-07-17T19:35:03.477 に答える