アルゴリズムの時間計算量分析: Big O 表記

[[354643]]

開発の際、アルゴリズムの品質をどのように評価し、アルゴリズムの効率をどのように説明すればよいのでしょうか。より一般的な表現方法は、プログラムの実行が速いか遅いかですが、これは比較的大まかな説明にすぎません。それを直感的かつ科学的に説明するにはどうすればよいでしょうか。

実行時間を使って非常にわかりやすく直感的に説明できると言う生徒もいるかもしれません。ただし、言語、コンパイラ、CPU が異なれば、プログラムの処理にかかる時間も異なります。実行時間を単純に使用してアルゴリズムの実行効率を表すことはできません。また、処理するデータが増えると、アルゴリズムの基本操作を繰り返す回数も増え、増加率はアルゴリズムごとに異なります。

数学は確かに優れたツールです。アルゴリズムの実行時間の増加を説明するために、さまざまな数式を使用して分析することができます。コンピュータ サイエンスには、アルゴリズムの効率性を特徴付ける特別な用語があり、それが今日学習する Big O 表記法です。 Big O は、アルゴリズムの実行にかかる時間を示すものではありません。アルゴリズムの実行時間の増加率を示します。つまり、アルゴリズムの実行時間はさまざまな率で増加します。これは漸近的時間複雑度とも呼ばれます。

これは次の式で表すことができます。

通常、時間の複雑さを説明するために次のような表現があります。

• O(1): 定数時間
• O(n): 線形時間
• O(log n): 対数時間
• O(n^2): 2次時間
• O(2^n): 指数時間
• O(n!): 階乗時間

それぞれの時間計算量は異なります。これらの時間計算量を詳しく見てみましょう。

ビッグOの複雑さ

オー(1)

O(1) は、一定の時間計算量を意味します。サイズ n の入力が与えられた場合、n の値が何であっても、アルゴリズムの最終的な実行時間は一定です。例えば：

 int関数( intn )
 {
    n++;
 n*2を返します。
 }

上記のプログラムでは、入力 n の値がどのように変化しても、プログラムの実行時間は常に一定です。単純化してみましょう。関数内の各ステートメントの実行時間が 1 の場合、実行時間の数式は次のようになります。

n がどれだけ大きくても、最終的な実行時間は 2 という固定値になります。実行時間は 2 ですが、ここでは O(1) を使用して表します。1 は定数を表します。

の上）

O(n) は線形時間計算量を表し、アルゴリズムの実行時間は入力 n のサイズに応じて線形に変化します。

 int関数( intn )
 {
整数 合計= 0;
 ( int i=0; i<n; i++)の場合
    {
合計=合計+ i;
    } 
 
戻る 合計;
 }

上記のプログラムでは、関数の実行時間は n に比例して変化します。

線形表現で表現できるこの状況では、O(n) を使用します。

なぜ式中の他の係数を省略できるのでしょうか? 主な理由は、n が無限大に近づくと、無限大の n に対する係数を無視できるためです。

O(n^2) の場合

O(n^2) は二次の時間計算量を表します。アルゴリズムの時間は、入力データ n の増加とともに二次的に増加します。

 int関数( intn )
 {
整数 合計= 0;
 ( int i=0; i<n; i++)の場合
    {
 ( int j=0; j<n; j++)の場合
        {
合計=合計+ i + j;
        }
    } 
 
戻る 合計;
 }

上記のプログラムは 2 つのループを持つプログラムであり、関数の実行時間は n の 2 乗です。

このタイプのプログラムの場合、O(n^2) と表現できます。ただし、この 2 層ループに加えて、3 層、4 層...n 層のループもあり、対応する複雑さは O(n^3)、O(n^4)...O(n^n) になります。

O(2^n)

O(2^n) は指数関数的な複雑さを表します。n が増加すると、アルゴリズムの実行時間は指数関数的に増加します。これは爆発的な増加の例です。

 int関数( intn )
 {
    n==0の場合は1を返します。 
 
 func(n) + func(n-1)を返す
}

上記のコードには 2 つの再帰呼び出しがあり、関数の実行時間は入力 n に指数的に関係します。

したがって、ここではO(2^n)を使用できます。

O(logn) です

O(log n) は対数時間計算量を意味し、アルゴリズムの実行時間と n は対数関係にあります。このタイプのアルゴリズムでは、プログラムの実行につれて、特定の機能を完了するためのステップが少なくなります。その中でも、私たちがよく知っている二分探索法は良い例です。たとえば、次のコードは順序付きリスト内の値の位置を見つけ、バイナリ検索を使用します。

 int関数( int a[], int  サイズ、 int数値)
 {
整数 左= 0;
整数 右=サイズ-1; 
 
    while(左<=右)
    {
 int中央 = (左+右)/2; 
 
        if(a[mid] > num)
        {
右= 中央 - 1;
        }
そうでない場合 (a[mid] < num)
        {
左= 中央 + 1;
        }
それ以外 
        {
数値を返します。
        }
    } 
 
 -1 を返します。
 }

最悪の場合、バイナリ検索で x 回分割した後、最後の要素が探している要素になります。次の式が得られます。

関数の実行時間は次のように表すことができます。

したがって、ここでは O(log n) を使用できます。

の上！）

階乗関係の複雑さの最も典型的な例は巡回セールスマン問題です。

n+1 都市を訪問したい旅行中のビジネスマンがいるとします。彼は進むべき道を選択する必要があります。この道の制約は、各都市を 1 回しか訪問できず、最後には元の出発都市に戻らなければならないことです。パス選択の目的は、すべてのパスの中で最小のパス長を取得することです。

この問題を解決する最も簡単な方法は、網羅的な列挙によってすべての順列と組み合わせをリストすることです。 n+1 個の都市がある場合、数学で学んだ順列と組み合わせの計算方法によれば、すべての組み合わせの数は n! であると計算できるため、この網羅的な方法に対応する時間計算量は O(n!) です。

この記事はWeChat公式アカウント「Will's Canteen」から転載したものです。下のQRコードからフォローできます。この記事を転載する場合は、Will’s Dashitang パブリックアカウントにご連絡ください。