O(n) アルゴリズムは実際にタイムアウトします。この時点で n はどのくらいの大きさでしょうか?

[[412223]]

生徒の中には、コンピューターの実行速度の概念がわからない人もいるかもしれませんが、コンピューターは非常に高速に動作するはずだと感じています。では、LeetCode でアルゴリズムの問​​題を解くときにタイムアウトするのはなぜでしょうか?

コンピューターは 1 秒間にいくつの操作を実行できるでしょうか? この質問について議論しましょう。

タイムアウトとは何ですか?

LeetCode でアルゴリズムを練習しているときに、「タイムアウト」と呼ばれるエラーに遭遇したことがあるはずです。

つまり、プログラムの実行時間が指定時間を超えています。一般的に、OJ（オンラインジャッジ）のタイムアウト時間は1秒です。これは、ユースケースデータを入力してから最大1秒以内に結果が得られなければならないことを意味します。LeetCodeの判定ルールはまだ明確ではありません。以下の説明の便宜上、タイムアウト時間は一時的に1秒に設定されています。

O(n) アルゴリズムを記述する場合、アルゴリズムの実行時間が 1 秒を超えるときの n の大きさを実際に見積もることができます。

n のサイズが十分に大きく、O(n) アルゴリズムを 1 秒以上実行する必要がある場合は、log(n) ソリューションを検討する必要があります。

ハードウェア構成から見たコンピュータのパフォーマンス

コンピュータの計算速度は主に CPU の構成によって決まります。2015 MacPro を例にとると、CPU 構成は 2.7 GHz デュアルコア Intel Core i5 です。

つまり、2.7GHz Pentium Dual Core、i5 プロセッサ、GHz は何を意味し、1Hz = 1/s、1Hz は CPU のパルス (状態の変化として理解でき、クロック サイクルとも呼ばれます) であり、ヘルツと呼ばれますが、1GHz は何ヘルツに相当しますか?

• 1GHz(メガヘルツ) = 1000MHz(メガヘルツ)
• 1MHz(メガヘルツ) = 100万ヘルツ

つまり、1GHz = 10億Hzなので、CPUは1秒間に10億回（10億クロックサイクル）パルスを発することができることになります。1クロックサイクルが1回のCPU操作であると単純に理解しないでください。

たとえば、1 + 2 = 3 の場合、CPU はこの操作を完了するために 4 回実行する必要があります。ステップ 1: レジスタに 1 を入れ、ステップ 2: レジスタに 2 を入れ、ステップ 3: 加算を実行し、ステップ 4: 3 を保存します。

さらに、コンピュータの CPU は、私たちが自分で書いたプログラムを実行するだけでなく、コンピュータのさまざまなプロセス タスクなどを実行します。私たちのプログラムは、プロセスのうちの 1 つにすぎません。

では、プログラムは実際に 1 秒間にコンピューター上でいくつの操作を実行できるのでしょうか?

テスト実験を行う

1 秒間にどれだけのデータを処理できるかを測定するテスト プログラムを作成する場合、注意すべき点が 3 つあります。

• CPU が各命令を実行するのに必要な時間は、実際には同じではありません。たとえば、CPU が加算演算と乗算演算を実行するのに必要な時間は実際には異なります。
• 現在、ほとんどのコンピュータ システムにはメモリ管理用のキャッシュ テクノロジが備わっているため、同じアドレスのデータに頻繁にアクセスする場合と、隣接していない要素にアクセスする場合にかかる時間も異なります。
• コンピューターは複数のプログラムを同時に実行し、各プログラムにはリソースを競合する異なるプロセス スレッドがあります。

影響を与える要因は多数ありますが、プログラムの実行時間について大まかな評価を行うことは可能です。

アルゴリズム 4 からの一節を引用します。

• ロケット科学者は、試験ロケットが海に着陸するのか、それとも都市に着陸するのかを大まかに知る必要がある。
• 医療研究者は薬物検査が被験者を死に至らしめるのか、それとも治癒させるのかを知る必要がある。

したがって、コンピュータ プログラマーを開発するソフトウェア エンジニアであれば、プログラムの実行に 1 秒かかるか 1 年かかるかを見積もることができなければなりません。

これは最も基本的なことなので、上記のエラーは大きな問題ではありません。

以下は C++ コードの例です。

テストハードウェア: 2015 MacPro、CPU 構成: 2.7 GHz デュアルコア Intel Core i5

時間計算量が O(n)、O(n^2)、O(nlogn) の 3 つの関数を実装し、加算演算を使用してテストを統合します。

 // の上）
 void 関数1(long long n) {
    長い長いk = 0;
 (long long i = 0; i < n; i++)の場合{
        関数
    }
 }

 // O(n^2)
 void 関数2(long long n) {
    長い長いk = 0;
 (long long i = 0; i < n; i++)の場合{
 (long j = 0; j < n; j++)の場合{
            関数
        }
    } 
 
 }

 // O(nlogn)
 void 関数3(long long n) {
    長い長いk = 0;
 (long long i = 0; i < n; i++)の場合{
 for (long long j = 1; j < n; j = j*2) { // ここでj=1であることに注意してください
            関数
        }
    }
 }

n のスケールが変わると、これら 3 つの関数の時間消費がどのように変化するかを見てみましょう。まず function1 をテストし、次に function2 と function3 をコメント アウトします。

 int main() {
    long long n; // データサイズ
    一方（1）{
        cout << "入力n:" ;
        cin >> n;
        ミリ秒 start_time = 継続時間キャスト<ミリ秒 >(
            システムクロック::now()。エポックからの時間()
        );
        関数1(n);
 // 関数2(n);
 // 関数3(n);
        ミリ秒 end_time = 継続時間キャスト<ミリ秒 >(
            システムクロック::now()。エポックからの時間()
        );
        cout << "所要時間:" << milliseconds(end_time) .count () - milliseconds(start_time) .count ()
            << " ms" << 終了;
    }
 }

実行中の効果を以下で確認してみましょう。

O(n) アルゴリズムの場合、コンピュータは 1 秒間に約 5 * (10^8) 回の計算を実行できます。O(n^2) アルゴリズムは 1 秒間に 5 * (10^8) 回の平方根を処理できるはずです。実験データは次のとおりです。

O(n^2)アルゴリズムは、コンピュータが1秒間に約22,500回の計算を実行できることを意味し、これは以前の推測を検証します。

O(nlogn)と仮定すると、1秒で処理できるデータのサイズはどれくらいでしょうか?

理論的には、logn の計算量は実際には非常に高速であるため、O(n) よりも 1 桁小さくなるはずです。実験データを見てみましょう。

O(nlogn) アルゴリズムの場合、コンピューターは 1 秒間に約 2 * (10^7) 回の計算を実行できます。これは予想どおりです。

これは私の個人用PCで計測したデータです。あまり正確とは言えませんが、桁は似ています。自分のパソコンでも計測できます。

全体的なテスト データは次のように構成されます。

O(logn) や O(n^3) などの時間計算量で 1 秒以内にどれだけのデータが処理できるかについては、自分でコードを書いてテストすることができます。

完全なテストコード

#include <iostream>
 #include <クロノ>
 #include <スレッド>
名前空間 std を使用します。
名前空間 chrono を使用します。
 // の上）
 void 関数1(long long n) {
    長い長いk = 0;
 (long long i = 0; i < n; i++)の場合{
        関数
    }
 } 
 
 // O(n^2)
 void 関数2(long long n) {
    長い長いk = 0;
 (long long i = 0; i < n; i++)の場合{
 (long j = 0; j < n; j++)の場合{
            関数
        }
    } 
 
 }
 // O(nlogn)
 void 関数3(long long n) {
    長い長いk = 0;
 (long long i = 0; i < n; i++)の場合{
 for (long long j = 1; j < n; j = j*2) { // ここでj=1であることに注意してください
            関数
        }
    }
 }
 int main() {
    long long n; // データサイズ
    一方（1）{
        cout << "入力n:" ;
        cin >> n;
        ミリ秒 start_time = 継続時間キャスト<ミリ秒 >(
            システムクロック::now()。エポックからの時間()
        );
        関数1(n);
 // 関数2(n);
 // 関数3(n);
        ミリ秒 end_time = 継続時間キャスト<ミリ秒 >(
            システムクロック::now()。エポックからの時間()
        );
        cout << "所要時間:" << milliseconds(end_time) .count () - milliseconds(start_time) .count ()
            << " ms" << 終了;
    }
 }

要約する

この記事では、LeetCode で問題を解くときにプログラムがタイムアウトする理由を詳細に分析し、ハードウェア構成から CPU 実行速度を大まかに把握します。次に、O(n) アルゴリズムを 1 秒間実行する場合、n がどの程度大きくなるかを調べる実験を行います。最後に、さまざまな時間計算量を与え、1 秒間に計算できる n のサイズを示します。

他のレコーダーの皆さんも、自分で実験やテストを行って、結果が私と似ているかどうかを確認することをお勧めします。

こうすることで、プログラムがタイムアウトしたときのデータの規模を全員が全体的に把握できるようになります。