3

私は時間の複雑さについていくつか読んでおり、基本をカバーしています。概念を強化するために、私が最近 SO で提供した回答を調べました。理由により、質問は終了しましたが、それは重要ではありません。回答の複雑さがわかりません。有用なフィードバックを得る前に質問が閉じられました。

タスクは、文字列内の最初の一意の文字を見つけることでした。私の答えは簡単なものでした：

public String firstLonelyChar(String input)
{
    while(input.length() > 0)
    {
        int curLength = input.length();
        String first = String.valueOf(input.charAt(0));
        input = input.replaceAll(first, "");
        if(input.length() == curLength - 1)
            return first;
    }
    return null;
}

イデオンの例へのリンク

私が最初に考えたのは、各文字を見て、次に各文字をもう一度見るreplaceAll()ので、O(n^2) になるということでした。

しかし、それが実際にどのように機能するかについて考えるようになりました。検査された文字ごとに、文字列内のその文字のすべてのインスタンスが削除されます。そのnため、常に縮小しています。それはどのように考慮されますか？それはO（log n）になりますか、それとも私が見ていないものがありますか？

私が求めているもの：

書かれたアルゴリズムの時間計算量はどのくらいですか? またその理由は?

私が求めていないこと：

私はそれを改善するための提案を探していません。おそらくこれを行うためのより良い方法があると思います。時間の複雑さの概念をよりよく理解しようとしていますが、最良の解決策を見つけることはできません。

4

4 に答える 4

4

最悪の時間の複雑さは、文字列aabb...など、各文字が正確に 2 回繰り返されることです。これは、アルファベットのサイズによって異なりますS。また、最初の文字列の長さに で注釈を付けましょうL。したがって、文字ごとに文字列全体を反復処理する必要があります。ただし、最初に行うと、文字列は size になりL、2 回目L-2などになります。L + (L-2) + ... + (L- S*2)全体として、操作の順序で実行する必要があります。つまりL*S - 2*S*(S+1)、L が より大きいと仮定し2*Sます。

ちなみに、アルファベットのサイズが一定である場合、コードの複雑さはO(L)(大きな定数ではありますが) です。

于 2013-02-20T16:17:43.303 に答える
1

最悪の場合はO(n^2)、nが入力文字列の長さである場合です。「aabbccddeeffg」のように、最後の文字を除いてすべての文字が2倍になる場合を想像してみてください。次に、n / 2ループの反復があり、への各呼び出しreplaceAllは残りの文字列全体をスキャンする必要があります。これもに比例しnます。

編集：Ivayloが指摘しているように、アルファベットのサイズが一定である場合、技術的にはO(n)、どの文字も2回しか考慮しないためです。

于 2013-02-20T16:16:08.557 に答える
1

マークしましょう：

m = 単語内の一意の文字数
n = 入力の長さ

これは複雑さの計算です
。メイン ループは最大で m回実行されます。m 個の異なる文字があるため
、.Replaceall は各サイクルで最大で O(n) 回の比較をチェックします。

合計: O(m*n)

O(m*n) サイクルの例: 入力 = aabbccdd,

m=4、n=8

アルゴリズムの段階:

1. input = aabbccdd, complex - 8
2. input = bbccdd, complex = 6
3. input = ccdd, complex = 4
4. input = dd, complex = 2

合計 = 8+6+4+2 = 20 = O(m*n)

于 2013-02-20T16:26:32.820 に答える
1

をアルファベットmのサイズとしn、文字列の長さを とします。最悪のケースは、文字列の文字をアルファベット文字の間に均一に分散させることです。つまり、アルファベットn / mの各文字に文字が含まれることになります。この量を でマークしましょうq。たとえば、文字列は文字間の文字aabbccddeeffgghhの均一な分布であるため、ここではとおよび各文字の文字があります。16a-hn=16m=8q=2

これで、アルゴリズムは実際にアルファベットの文字を処理し (文字列に表示される順序を使用するだけです)、反復ごとに文字列の長さ ( ) を調べて( )nだけ縮小する必要があります。したがって、最悪の場合に実行する操作の数は次のとおりです。qn -= q

s = n + n-(1*q) + ... + n-((m-1)*q)

算術級数の最初の要素のs合計であることがわかります。m

s = (n + n-((m-1)*q) * m / 2 =  
    (n + n-((m-1)*(n/m)) * m / 2 ~ n * m / 2
于 2013-02-20T17:02:23.800 に答える