[この一連のブログ投稿では、一般的なデータ構造と対応するアルゴリズムを分析および要約し、各ブログ投稿でいくつかの関連する一流インターネット企業の面接/筆記試験の質問を提供して、学習内容を統合し、ギャップを埋めるのに役立ちます。プロジェクトアドレス: https://github.com/absfree/Algo。私の個人的なレベルが限られているため、説明には不明瞭な部分や不正確な部分がどうしてもあります。訂正していただければ幸いです。ありがとうございます:)]

1. はじめに

データ構造とアルゴリズムをさらに研究する前に、まずアルゴリズム分析の一般的な方法を習得する必要があります。アルゴリズム分析には主にアルゴリズムの時間と空間の複雑さの分析が含まれますが、アルゴリズムの実際の実行パフォーマンスに重点を置くこともあります。さらに、アルゴリズムの視覚化は、アルゴリズムの実際の実行プロセスを理解するのに役立つ実用的なスキルです。このスキルは、より抽象的なアルゴリズムを分析するときに特に役立ちます。このブログ記事では、まず実験を設計してアルゴリズムの実際の動作パフォーマンスを定量化する方法を紹介し、次にアルゴリズムの時間計算量の分析方法を紹介し、さらにアルゴリズムのパフォーマンスを非常に便利に予測できる乗数実験も紹介します。もちろん、この記事の最後では、学んだことを定着させて実践するために、インターネット関連の初級レベルの面接/筆記試験問題をいくつか一緒に解いていきます。

2. アルゴリズム分析の一般的な方法

1. アルゴリズムの実際のパフォーマンスを定量化する

アルゴリズムの時間と空間の複雑さの分析方法を紹介する前に、まずアルゴリズムの実際の実行パフォーマンスを定量化する方法を紹介します。ここでは、アルゴリズムのパフォーマンスを測定するために選択した定量的な指標は、実際の実行時間です。通常、この実行時間は、アルゴリズムが解決しようとしている問題の大きさに関係します。たとえば、100 万個の数字をソートするには、通常、10 万個の数字をソートするよりも時間がかかります。したがって、アルゴリズムの実行時間を観察するときは、アルゴリズムが解決する問題の規模も考慮し、問題の規模の拡大に伴ってアルゴリズムの実際の実行時間がどのように増加するかを観察する必要があります。ここでは、書籍『アルゴリズム（第 4 版）』（Douban）の例を使用します。コードは次のとおりです。

公共 クラスThreeSum {
公共 静的  intカウント( int [] a) {
 N = a.length;
整数値 = 0 ;
 ( int i = 0 ; i < N; i++)の場合{
 ( int j = i + 1 ; j < N; j++)の場合{
 ( int k = j + 1 ; k < N; k++)の場合{
 (a[i] + a[j] + a[k] == 0 )の場合{
                        cnt++;
                    }
                }
            }
        }
 cntを返します。
    } 
     
公共 静的  void main(String[] args) {
 int [] a = StdIn.readAllInts();
        StdOut.println(count(a));
    }
 }

上記のコードで使用されている 2 つのクラス StdIn と StdOut は、https://github.com/absfree/Algo にあります。上記のコードの機能は、標準の int[] 配列内で合計が 0 になる 3 つの整数タプルの数をカウントすることであることがわかります。使用されるアルゴリズムは非常に直接的です。配列を最初から走査し、毎回 3 つの数値を取得します。合計が 0 の場合、カウントは 1 ずつ増加します。返されるカウント値は、合計が 0 である 3 つ組の数です。ここでは、それぞれ 1000、2000、4000 個の整数を含む 3 つのファイル (これらのファイルは上記のプロジェクト アドレスにあります) を使用して、上記のアルゴリズムをテストし、問題のサイズが大きくなるにつれて実行時間がどのように変化するかを観察します。

プロセスの実行時間を直接測定する方法は、プロセスの実行前と実行後に現在の時刻を 1 回ずつ取得し、その 2 つの差がプロセスの実行時間となることです。プロセス自体の実行時間が短い場合、この測定方法には多少の誤差が生じる可能性がありますが、このプロセスを複数回実行して平均を取ることで、この誤差を軽減したり、無視したりすることができます。実際に上記のアルゴリズムの実行時間を測定してみましょう。関連するコードは次のとおりです。

公共 静的  void main(String[] args) {
 int [] a = In.readInts(args[ 0 ]);
長い開始時間 = System.currentTimeMillis();
整数カウント = count(a);
長いendTime = System.currentTimeMillis();
ダブルタイム = (終了時間 - 開始時間) / 1000.0 ;
        StdOut.println( "結果は: " + count + "で、" + time + "秒かかります。" );
    }

それぞれ1000、2000、4000の整数を入力として使用し、実行結果は次のとおりです。

結果は 70 で、1.017 秒かかります。//1000 個の整数
 
結果は 528 で、7.894 秒かかります。//2000 個の整数
 
結果は 4039 で、64.348 秒かかります。//4000 個の整数

上記の結果から、問題のサイズが元の 2 倍になると、実際の実行時間は元の約 8 倍になることが大まかにわかります。この現象に基づいて、プログラムの実行時間と問題のサイズ N の間の関数関係は T(N) = k*(n^3) であると推測できます。

この関係では、n が 2 倍になると、T(N) は 8 倍に増加します。では、ThreeSum アルゴリズムの実行時間と問題のサイズは、上記の関数関係を満たしているでしょうか?アルゴリズムの時間計算量について説明した後で、この質問に戻ります。

2. アルゴリズムの時間計算量分析

（１）基本概念

アルゴリズムの時間計算量に関して、ここでは関連する 3 つの記号表記法について簡単に紹介します。

1 つ目は Big O 表記法と呼ばれ、実行時間の「漸近的上限」、つまり最悪の場合のアルゴリズムの実行時間の上限を示します。これは次のように定義されます: f(n) と g(n) について、すべての n > N0 に対して |f(n)| < c * g(n) となる定数 c と N0 が存在する場合、f(n) は O(g(n) と呼ばれます。
3 番目はビッグ Ω 表記法と呼ばれ、実行時間の「漸近下限」、つまりアルゴリズムの最悪ケースの実行時間の下限を示します。これは次のように定義されます: f(n) と g(n) に対して、すべての n > N0 に対して |f(n)| > c * g(n) となる定数 c と N0 が存在する場合、f(n) は Ω(g(n)) と呼ばれます。
3 番目は Big Θ 表記法と呼ばれ、実行時間の「漸近境界」を決定します。定義は次のとおりです: f(n) と g(n) について、定数 c と N0 が存在し、すべての n>N0 に対して、|f(n)| = c * g(n) である場合、f(n) は Θ または Θ(g(n)) と呼ばれます。

Big O 表記法は、日常のアルゴリズム分析で最もよく使用されます。以下では、アルゴリズムの時間計算量を分析する具体的な方法を紹介します。Big O 表記法の概念に馴染みがない場合は、こちらの記事を読むことをお勧めします: http://blog.jobbole.com/55184/。

（２）時間計算量の解析方法

このセクションでは、上記の ThreeSum プログラムを例に、アルゴリズムの時間計算量の分析方法を紹介します。読みやすくするために、上記のプログラムを次に示します。

公共 静的  intカウント( int [] a) {
 N = a.length;
整数値 = 0 ;
 ( int i = 0 ; i < N; i++)の場合{
 ( int j = i + 1 ; j < N; j++)の場合{
 ( int k = j + 1 ; k < N; k++)の場合{
 (a[i] + a[j] + a[k] == 0 )の場合{
                        cnt++;
                    }
                }
            }
        }
 cntを返します。
    }

時間計算量分析法を紹介する前に、まずアルゴリズムの実行時間が何に依存するかを明確にしましょう。直感的に言えば、アルゴリズムの実行時間は、すべてのプログラム ステートメントを実行するのにかかる時間の合計です。しかし、実際の分析では、すべてのプログラムステートメントの実行時間を考慮する必要はありません。最も時間のかかる部分、つまり最も頻繁に実行され、最も時間のかかる操作に焦点を当てる必要があります。つまり、プログラムの時間計算量を分析する前に、まずプログラム内のどのステートメントが実行時間の大部分を占めるかを判断する必要があり、時間のかかる操作は無視できますが、実行回数は一定回数のみです (問題のサイズに関係なく)。最も時間のかかる操作を選択し、これらの操作が実行される回数を数えることでアルゴリズムの時間計算量を推定します。このプロセスについて、以下で詳しく説明します。

まず、上記のコードの 1 行目と 2 行目のステートメントは 1 回しか実行されないため、無視できます。すると、4 行目から 12 行目は 3 層のループであり、最後のループ本体には if ステートメントが含まれていることがわかります。つまり、この if 文は上記のコードの中で最も時間のかかる文です。次に、このアルゴリズムの時間計算量を見積もるには、if 文の実行回数を数えるだけで済みます。上記のアルゴリズムでは、問題のサイズは N (入力配列に含まれる要素の数) であり、if ステートメントの実行回数が N に関連していることもわかります。 if ステートメントは N * (N - 1) * (N - 2) / 6 回実行されるため、このアルゴリズムの時間計算量は O(n^3) であると結論付けるのは難しくありません。これは、実行時間と問題のサイズ (T(n) = k * n ^ 3) 間の機能的関係についての以前の推測も裏付けています。このことから、アルゴリズムの時間複雑度は、問題の規模が大きくなるにつれてアルゴリズムの実行時間がどれだけ速く増加するかを表していることもわかります。日常的に使用される場合、Big O 表記法は通常、最悪の場合のアルゴリズムの実行時間の厳密な上限を示すものではありません。代わりに、通常の状況下でのアルゴリズムの漸近的パフォーマンスの上限を表すために使用されます。Big O 表記法を使用して最悪の場合のアルゴリズムの実行時間の上限を説明する場合、通常は「最悪の場合」という修飾語を追加します。

上記の分析により、分析アルゴリズムの時間計算量は 2 つのステップのみであることがわかります (象を冷蔵庫に入れるよりも 1 ステップ少ないです :)):

キー操作が実行された回数を分析します。

上記の例では、入力した整数配列が何であっても、if ステートメントの実行回数は変わらないことがわかります。つまり、上記のアルゴリズムの実行時間は入力とは関係ありません。ただし、一部のアルゴリズムの実際の実行時間は、入力内容に大きく依存します。この問題については以下で紹介します。

3. アルゴリズムの予想実行時間

アルゴリズムの予想される実行時間は、通常の状況下でアルゴリズムがどのくらいの時間実行されるかとして理解できます。多くの場合、最悪のケースと最良のケースが発生する確率は比較的低く、一般的な状況に遭遇することが多いため、最悪のケースでのアルゴリズムの実行時間の上限よりも、アルゴリズムの予想される実行時間の方が重要です。たとえば、クイック ソート アルゴリズムとマージ ソート アルゴリズムの時間計算量は O(nlogn) ですが、同じ問題規模ではクイック ソートの方がマージ ソートよりも高速であることが多いため、クイック ソート アルゴリズムの予想実行時間はマージ ソートよりも短くなります。しかし、最悪の場合、クイックソートの時間計算量は O(n^2) になります。クイックソートアルゴリズムは、実行時間が入力に依存するアルゴリズムです。この問題では、ソートする入力配列の順序を乱すことで、最悪のケースを回避できます。

4. レート実験

次回は、アルゴリズム（第4版）（豆瓣）に掲載されている「掛け算の実験」を紹介します。この方法により、プログラムのパフォーマンスを簡単かつ効果的に予測し、実行時間の増加のおおよその桁数を決定できます。レート実験を正式に紹介する前に、まず「成長の大きさの順序」の概念を簡単に紹介しましょう (これも「アルゴリズム」という本から引用)。

N が増加するにつれて f(N) で割った結果が 1 に近づくすべての関数を表すために ~f(N) を使用します。 g(N)~f(N)を使用して、Nが増加するにつれてg(N) / f(N)が1に近づくことを示します。通常使用する近似値は g(N) ~ a * f(N) です。 f(N)をg(N)の増加次数と呼びます。

ThreeSum プログラムを例に挙げてみましょう。g(N) は、入力配列のサイズが N のときに if ステートメントが実行される回数を表すものとします。上記の定義によれば、g(N) ~ N ^ 3 が得られます (N が正の無限大に近づくと、g(N) / N^3 は 1 に近づきます)。したがって、g(N) の増加の順序は N^3 です。つまり、ThreeSum アルゴリズムの実行時間の増加の順序は N^3 です。

さて、掛け算の実験を正式に紹介しましょう（以下の内容は主に前述の書籍「アルゴリズム」からの引用であり、若干の個人的な理解も加えています）。まず、ウォームアップルーチンを実行しましょう。

公共 クラスDoublingTest {
公共 静的 ダブルタイムトライアル( int N) {
整数最大値 = 1000000 ;
 int [] a =新しい 整数[N];
 ( int i = 0 ; i < N; i++)の場合{
            a[i] = StdRandom.uniform(-MAX, MAX);
        }
長い開始時間 = System.currentTimeMillis();
整数count = ThreeSum.count(a);
長いendTime = System.currentTimeMillis();
ダブルタイム = (終了時間 - 開始時間) / 1000.0 ;
戻り時間;
    } 
     
公共 静的  void main(String[] args) {
 ( int N = 250 ; true ; N += N) {
ダブルタイム = timeTrial(N);
            StdOut.printf( "%7d %5.1f\n" , N, 時間);
        }
    }
 }

上記のコードは 250 から開始し、ThreeSum 問題のサイズを毎回 2 倍にして、ThreeSum の実行ごとに問題のサイズと対応する実行時間を出力します。上記のプログラムを実行した場合の出力は次のようになります。

 250 0.0
 500 0.1
 1000 0.6
 2000 4.3
 4000 30.6

上記の出力が理論値と異なる理由は、実際の動作環境が複雑かつ変化しやすく、多くの偏差が生じるためです。この偏差を最小限に抑える方法は、上記のプログラムを複数回実行し、平均値を取ることです。上記のウォームアップ プログラムを前置きとして、この「プログラムの実行パフォーマンスを簡単かつ効果的に予測し、実行時間の増加のおおよその順序を決定する」方法を正式に導入できるようになりました。実際、この方法は上記の DoublingTest プログラムに基づいています。一般的なプロセスは次のとおりです。

実際の状況で起こり得るさまざまな入力を生成するための[入力ジェネレータ]を開発します。
次の DoublingRatio プログラムを繰り返し実行し、time/prev の値が限界 2^b に近づくと、アルゴリズムの成長順序は約 N^b (b は定数) になります。

DoublingRatio の手順は次のとおりです。

乗算プログラムを実行すると、次の出力が得られます。

 0.0 2.0
 0.1 5.5
 0.5 5.4
 3.7 7.0
 27.4 7.4
 218.0 8.0

time/prev は 8 (2^3) に収束することがわかります。では、入力を 2 倍にしてプログラムを繰り返し実行すると、実行時間の比率が一定に近づくのはなぜでしょうか?答えは次の[乗法定理]です。

T(N) ~ a * N^b * lgNの場合、T(2N) / T(N) ~2^bとなります。

上記の定理の証明は非常に簡単です。N が正の無限大に近づくときの T(2N) / T(N) の極限を計算するだけです。このうち、「a * N^b * lgN」は、基本的に一般的なアルゴリズムの成長順序をカバーします（aとbは定数です）。注目すべきは、アルゴリズムが NlogN のオーダーで増大する場合、そのレート テストを実行すると、実行時間の増加オーダーが約 N であることがわかるということです。実際、これは矛盾ではありません。乗算実験の結果に基づいて、アルゴリズムが特定の数学モデルに準拠していると推測することはできないからです。対応するアルゴリズムのパフォーマンスを大まかに予測することしかできません (N が 16000 から 32000 の間である場合、14N は NlgN に非常に近くなります)。

5. 償却分析

データ構造とリンク リストの詳細な理解のところで前述した ResizingArrayStack について考えてみましょう。これは動的なサイズ変更をサポートし、最下層に配列が実装されたスタックです。スタックに要素を追加するたびに、配列がいっぱいかどうかを確認します。いっぱいの場合は、2 倍のサイズの新しい配列を作成し、元の配列のすべての要素を新しい配列にコピーします。配列がいっぱいでない場合、プッシュ操作の複雑さは O(1) であることがわかっています。ただし、プッシュ操作によって配列がいっぱいになると、新しい配列を作成してそれをコピーする作業により、プッシュ操作の複雑さが突然 O(n) に増加します。

上記の状況では、プッシュの複雑さが O(n) であるとは言えません。通常、プッシュの「平均複雑さ」は O(1) であると考えられます。これは、結局のところ、n 回のプッシュ操作ごとに「新しい配列への要素のコピー」が 1 回トリガーされるため、これらの n 回のプッシュでこのコストが償却されるからです。この一連のプッシュごとに、償却コストは O(1) です。すべての操作の合計コストを記録し、それを操作の合計数で割ってコストを償却するこの方法は、償却分析（または償却分析とも呼ばれます）と呼ばれます。

3. 有名企業の実践的な面接の質問に挑戦する

先ほどアルゴリズム分析のテクニックをいくつか紹介しましたが、ここで学んだことを実践し、一流インターネット企業のアルゴリズム分析に関する面接/筆記試験の問題を解いてみましょう。

【テンセント】次のアルゴリズムの時間計算量は____です
int foo(int n) {
(n <= 1) の場合 {
1 を返します。
}
n * foo(n - 1) を返します。
}

この問題ではアルゴリズムの時間計算量を分析する必要があることがわかったので、最初に行う必要があるのは主要な操作を決定することです。ここで主要な操作は明らかに if ステートメントであるため、if ステートメントが実行される回数を決定するだけで済みます。まず、これは再帰的なプロセスであることがわかります。foo は、foo の実際のパラメータが 1 以下になるまで自分自身を呼び出し続け、その後 foo は 1 を返し、if ステートメントは実行されなくなります。このことから、if ステートメントが n 回呼び出されることがわかります。したがって、時間の計算量は O(n) です。

【JD.com】次の関数の時間計算量は____です
void 再帰(int n, int m, int o) {
(n <= 0)の場合{
printf("%d, %d\n", m, o);
} それ以外 {
再帰(n - 1, m + 1, o);
再帰(n - 1, m, o + 1);
}
}

この質問は明らかに前の質問よりも難しいので、段階的に解いていきましょう。まず、重要な操作は if 文なので、if 文が実行される回数を決定するだけで済みます。上記の関数は、n > 0 の場合に自分自身を再帰的に呼び出します。必要なのは、再帰的な基本ケース (つまり、n <= 0) に到達する前に、if ステートメントが何回実行されるかを判断することです。 if文の実行回数をT(n, m, o)とすると、次の式が得られます: T(n, m, o) = T(n-1, m+1, o) + T(n-1, m, o+1) (n > 0の場合)。基本ケースはパラメータ m および o とは何の関係もないことが分かるので、上記の式をさらに T(n) = 2T(n-1) に簡略化できます。これにより、T(n) = 2T(n-1) = (2^2) * T(n-2) が得られます。したがって、上記のアルゴリズムの時間計算量は O(2^n) であることがわかります。

【JD.com】次のプログラムの時間計算量は ____ です (m > 1、e > 0)
x = メートル;
＞y = 1;
(x - y > e) である間 {
ｘ = （ｘ + ｙ） / ２；
y = m / x;
}
印刷(x);

上記のアルゴリズムの重要な操作は、while ステートメント内の 2 つの代入ステートメントです。これらの 2 つのステートメントが実行される回数をカウントするだけで済みます。 x - y > e のとき、while 文本体の文が実行され、x = (x + y) / 2 によって x が減少し続けることがわかります (y<<x のとき、この文を 1 回実行すると、x は元の値の約半分になります)。y の値が 1 に固定されていると仮定すると、ループ本体の実行回数は ~logm です。実際の状況では、各ループ本体の開始時に y が m / x に割り当てられます。この値は常に、前のループの y の値よりも大きくなります。このように、xy の値は小さくなるため、上記のアルゴリズムの時間計算量は O(logm) になります。

【Sogou】アルゴリズムの計算時間が再帰関係 T(n) = 2T(n/2) + n, T(1) = 1 で表現できると仮定すると、アルゴリズムの時間計算量は ____ です。

質問に示されている再帰関係によれば、さらに次の式が得られます: T(n) = 2(2T(n/4) + n/2) + n = ... 再帰式をさらに展開すると、アルゴリズムの時間計算量は O(nlogn) であることがわかります。ここでは詳細なプロセスを投稿しません。

IV. 参考文献

アルゴリズム（第4版）（豆瓣）