0 
int maxValue = m[0][0];         
for (int i = 0; i < N; i++) 
{               
    for (int j = 0; j < N; j++) 
    {                   
        if ( m[i][j] >maxValue )        
        {                   
            maxValue = m[i][j];     
        }                       
    }                   
}                   

cout<<maxValue<<endl;           

int sum = 0;                
for (int i = 0; i < N; i++)     
{                   
    for (int j = 0; j < N; j++)     
    {                   
        sum = sum + m[i][j];            
    }                   
} 

cout<< sum <<endl;

上記のコードの場合、実行時間の増加としてO（n2）を取得しました。取得した方法は次のとおりです。

MAX [O（1）、O（n2）、O（1）、O（1）、O（n2）、O（1）]

両方のO（n2）はforループ用です。この計算は正しいですか？

このコードを次のように変更した場合：

int maxValue = m[0][0]; 
int sum = 0;
for (int i = 0; i < N; i++)         
{                       
    for (int j = 0; j < N; j++)         
    {                       
    if ( m[i][j] > maxValue )       
        {                   
        maxValue = m[i][j];     
        }               
        sum += m[i][j];
    }                   
}   

cout<<maxValue<<endl;   
cout<< sum <<endl;

それでもビッグOはO（n2）でしょ？つまり、Big Oは、入力データのサイズに応じて時間がどのように増加するかを示しているにすぎませんか？アルゴリズムの書き方ではありませんか？

4

3 に答える 3

2

これは私には宿題の質問のように少し感じますが...

Big-Ohはアルゴリズムに関するものであり、具体的には、入力データのサイズが大きくなるにつれて、アルゴリズムによって実行されるステップ数（または使用されるメモリの量）がどのように大きくなるかについてです。

あなたの場合、入力のサイズとしてNを使用していますが、2次元配列NxNがあるため、混乱を招きます。実際、アルゴリズムはこのデータに対して1つまたは2つのパスしか作成しないため、O（n）と呼ぶことができます。この場合、nは2次元入力のサイズです。

しかし、質問の核心に答えるために、最初のコードはデータを2回パスし、2番目のコードは1回のパスで同じ作業を行います。ただし、Big-Ohの考え方は、成長の順序を与える必要があるということです。つまり、特定のコンピューターの実行速度とは無関係です。つまり、私のコンピューターはあなたのコンピューターの2倍の速度である可能性があるので、2番目のコードを実行するのとほぼ同時に最初のコードを実行できます。したがって、これらの種類の違いを無視し、両方のアルゴリズムがデータに対して固定数のパスを作成すると言いたいので、「成長の順序」の目的では、1パス、2パス、3パスは問題ではありません。それはすべて1パスとほぼ同じです。

NxN入力について考えることなく、これについて考える方がおそらく簡単です。N個の数値の単一のリストについて考えて、最大値を見つける、またはリストを並べ替えるなど、何かを実行したいとします。リストに100個のアイテムがある場合は、100ステップで最大値を見つけることができ、1000個のアイテムがある場合は、1000ステップでそれを行うことができます。したがって、成長の順序は線形です入力のサイズ：O（n）。一方、並べ替える場合は、次に挿入するアイテムが見つかるたびにデータをほぼ完全にパスするアルゴリズムを作成することができます。これは、の各要素に対してほぼ1回実行する必要があります。リスト、つまりnが長さnのリストを通過するようにするので、O（n ^ 2）になります。リストに100個のアイテムがある場合、それはおよそ10 ^ 4ステップであり、リストに1000個のアイテムがある場合、それはおよそ10^6ステップです。つまり、これらの数値は入力のサイズと比較して非常に速く成長するという考えです。したがって、私がはるかに高速なコンピューター（たとえば、あなたのコンピューターより10年優れたモデル）を持っていても、 2倍または10倍、さらには100倍または1000倍の長さのリストでも最大の問題。しかし、O（n ^ 2）アルゴリズムのソート問題については、あなたのコンピュータよりも10年または20年優れているコンピュータでも、100倍または1000倍の長さのリストを作成しようとすると、あなたを打ち負かすことができません。これがBig-Ohのアイデアであり、これらの「比較的重要でない」速度の違いを除外し、より一般的/理論的な意味で、特定のアルゴリズムが特定の入力サイズで実行する作業量を確認できます。

もちろん、実際には、あるコンピュータが別のコンピュータよりも100倍高速であることが大きな違いを生む可能性があります。最大入力サイズを固定して特定の問題を解決しようとしていて、コードが上司が要求する速度の1/10で実行されていて、10倍高速で実行される新しいコンピューターを入手した場合、問題は解決されます。より良いアルゴリズムを書く必要があります。しかし、重要なのは、より大きな（はるかに大きな）データセットを処理したい場合、より高速なコンピューターを待つことはできないということです。

于 2012-04-29T09:31:03.843 に答える
1

表記は、入力サイズに基づいてアルゴリズムを実行するのbig Oにかかる最大時間の上限です。したがって、基本的に2つのアルゴリズムの最大実行時間はわずかに異なりますが、big O表記は同じです。

理解する必要があるのは、入力サイズに基づいて線形である実行時間関数の場合、o（n）として大きなo表記があり、2次関数は常にo（n ^ 2）として大きなo表記を持つということです。

したがって、実行時間がちょうどn、つまり1つの線形パスである場合、大きなo表記はo（n）のままであり、実行時間が6n + cである場合は6つの線形パスであり、定数時間cはo（n）のままです。

上記の場合、ループのメモリ位置にスキップする必要がある回数が少ないため、2番目のコードはより最適化されています。したがって、これにより実行が改善されます。ただし、両方のコードの実行時間は、まだ漸近的o(n^2)です。

于 2012-04-29T09:12:39.307 に答える
0

はい、どちらの場合もO（N ^ 2）です。もちろん、O（）の時間計算量は、アルゴリズムの記述方法によって異なりますが、上記のバージョンは両方ともO（N ^ 2）です。ただし、実際にはN ^ 2は入力データのサイズ（N x N行列）であるため、これは線形時間アルゴリズムO（n）としてより適切に特徴付けられることに注意してください。ここで、nは入力のサイズ、つまりnです。 =NxN。

于 2012-04-29T09:09:01.000 に答える