私は時間計算量に関する Coursera コースを学習しています。 ビデオでこれに遭遇しましたが、何かが間違っていると思います。 「それでは、実行時間が n にほぼ比例するアルゴリズムがあり、それを約 1 ギガヘルツで動作するマシン上で実行したいとします。計算を 1 秒以内に完了するには、どの程度の大きさの入力を処理できるでしょうか。 ? ” (1GHZ CPU (10^9 サイクル/秒))
「まあ、約 n のサイズで実行すると、1 秒以上かかる前に約 10 億のサイズの入力を処理できます。」 (10^9 / 10^9)
「n の 2 乗のように実行される場合、状況はさらに悪化します。1 秒以上かかり始める前に、約 30,000 のサイズの入力しか処理できません。」 n = 30000、(30000)^2/10^9 = 0.9秒～1秒
「入力のサイズが 2 から n までの場合、それは信じられないほど悪いです。1 秒間に約 30 のサイズの入力しか処理できません。」 2^30/10^9 ~ 1.07 秒
n log(n) の複雑さでは、入力サイズ n が 10^9 の場合、10^9 * log(10^9) / 10^9 = 9 秒かかるはずですよね。 どういうわけかビデオでは30秒が表示されます。 また、n = 10^7.5 の場合、実行時間は 1 秒であるとも言われていますが、これも私の計算では間違っています。
n、n^2、2^nの複雑さですべてのケースを計算しましたが、すべてが正しく、nlog(n)のケースだけが台無しでした
詳細については次の写真を参照してください。 https://i.upanh.org/2022/04/11/nlogn.jpg[^]
コースビデオのリンク (3:40 ～ 5:00 の部分): https://www.coursera.org/lecture/algorithmic-toolbox/asymptotic-notation-zI8dH[^]
私が見たコースビデオと同じになるように質問を編集しました
私が試したこと：
I calculated every case with the n, n^2, 2^n complexity and everything was right, only nlog(n) case messed up
解決策 1
引用：入力サイズ n が 10^9 の場合、10^9 * log(10^9) / 10^9 = 9 秒かかりますよね。
いいえ ！ 少なくとも Big O 記法自体から実行時間を計算することはありません。
Big O 表記法は、ランタイムではなく、アルゴリズムのカテゴリの複雑さを直接ではなく示します。
特定のデータ サイズのランタイムがある場合、Big O の複雑さにより、別のデータ サイズのランタイムを評価できます。
20 から 10^6 までのデータのタイミングが 1 秒であるということは、意味のあるタイミングを得るにはミリ秒のタイミングに切り替える必要があることを意味します。
解決策 2
おおきい O 実行の正確な時刻は示されません。 たとえば、を参照してください。 ビッグオー表記 – Wikipedia[^] (プロパティ セクション、 定数による乗算）。
解決策 3
他の人の意見に付け加えますと、とにかくクロック サイクルを実行時間と直接同一視することはできません。一部のマシン操作では実行に n サイクルかかりますが、他の操作は n * 2 かかる場合があります。さらに、最新のプロセッサはパイプライン化されているため、一部の命令は実行されません。他の命令が実行中、キャッシュされている間に開始される可能性があります。そのため、実行時間は、命令が最後に実行された時間と、そのデータが L1、L2、または L3 キャッシュで利用可能かどうか、実行する空きコアの可用性、およびその他のホストによって異なります。詳細。
「クロック速度が X であるため、実行時間は X * Y です」とだけ言うことはできません。影響を与える要因は他にもたくさんあります。
解決策 5
ログなら30秒くらいがちょうどいい2(n)。 ログ2(1000) ~= 10。
編集: O(n log(n)) アルゴリズムでは、多くの場合、問題を再帰的に半分に分割し、それぞれの部分を個別に解決し、その後、解決策を組み合わせます。 これがログに記録される理由です2 通常は暗示されています。 マージソートが良い例です。
解決策 6
大きな O 表記は、実行時間がどのようになるかを示すだけです。 変化 問題の「サイズ」が変更された場合、特定のケースに対する実際の推定値は得られません。
つまり、未知の要素があるので、例えば、 O(n2) 意味するかもしれない
time_needed = constant * n * n
ここで、定数の値が何であるかを誰も教えていないため、time_needed の具体的な値はありません。
この例は、2 倍の大きさの問題は解決するのに 4 倍の時間がかかることを示しているだけです。
コメント