2

以下のコード例の 2 つのバリアントのランタイムの複雑さが技術的に同じかどうかを知りたいです。

例（そして、ポイントを作るために、文字列の長さが偶数であるとしましょう）：

//counting how many times char 'c' appear in the string s

String s = "ascdwcccdweccaaa"; //the "array", contain char 'c' 6 times

int counter = 0; //times char 'c' appear in the string

for(int i=1; i <= s.length()/2; i++)
    {
    if(s.charAt(i-1) == 'c')
        counter++;
    if(s.charAt(s.length()-i) == 'c')
        counter++;
    }

これに比べると…

for(int i=0; i < s.length(); i++)
    if(s.charAt(i) == 'c')
        counter++;

最初の例では、インデックスを使用して、配列の最後と最初の両方から、配列の中央に到達するまでチェックします (おそらくO(n/2))

2番目の例では、配列内のすべての文字を最初から最後まで厳密にチェックしています（おそらくO(n)）

最初の例では two を使用する必要がifsあり、2 番目の例では one を使用する必要がありますif。

これら 2 つのコードは、時間の複雑さにおいて技術的に同一ですか? ifs(最初の例で配列の半分だけを渡すときに2 つを使用するという事実を考えると、それらは「均一化」されますか?)

4

3 に答える 3

4

両方のプログラムのO(n)複雑さはまったく同じです。実際には、同じ順序であるため、O(n/2)等しいです。O(n)しかし、それを考慮しても、2 倍の作業を実行する反復が 2 倍少なくなります。合計は同じです。

したがって、プログラムの複雑さは同じです。ただし、最初のものにはいくつかの欠点があります。

  • 読むのがより複雑で、明確ではありません

  • 要素数が奇数の配列はどうですか？

  • JVM は、いくつかの高度な最適化を行う可能性があります。境界チェック (VM は、単に配列全体を繰り返し処理していることを検出した場合でも、常に境界をチェックするとは限りません)。この空想を使用すると、オプティマイザが混乱する可能性があります。

そうは言っても、コードを最適化しようとしているときに、コードが読みにくくなり、正しくなく、おそらく遅くなりました。

于 2012-06-06T19:52:26.687 に答える
1

O(n) と O(n/2) はどちらも同じ成長率 (線形) であるため、時間計算量も同じです。

http://en.wikipedia.org/wiki/Big_O_notation

于 2012-06-06T19:52:15.277 に答える
0

1/2==0すべてのアトミック操作のコストが 1 であると仮定すると、最初のアルゴリズムが1 の長さで失敗するため、アルゴリズムは同等ではありません ( )。最初のアルゴリズムは次のような複雑さを持ちます。

for (int i=1;                          // 1
    i <= s.length()/2;                 // 3 + ⎡n/2⎤ · ( 3
    i++) {                             //     1
    if(s.charAt(i) == 'c')             //     3
        counter++;                     //     1
    if(s.charAt(s.length()-i) == 'c')  //     4
        counter++;                     //     1
}                                      // )

n ≥ 8 の場合、一様コストの合計は 4 + ⎡<em>n/2⎤·13 ≤ 14·⎡<em>n/2⎤ です。また、14·⎡<em>n/2⎤ ≤ 28· nであるため、 28 は定数係数で、アルゴリズムは Ο( n ) にあります。

または、すでにコメントとして述べたように: n /2 · 2 はまだnに等しいです。

于 2012-06-06T20:36:47.170 に答える