performance - アルゴリズムの速度とコンピューターの速度が与えられた場合、実行時間をどのように見つけますか?

Question

私は現在、Big-O と実行時間を扱う課題に取り組んでいます。非常に簡単に思える質問が 1 つありますが、正しく行っているかどうかはわかりません。残りの問題はかなり難しく、ここで何かを見落としているような気がします。

まず、次のようなものがあります。 アルゴリズム A の実行時間は 50n^3 です。コンピューター A。1 操作あたりの速度は 1 ミリ秒です。1 回の操作で 2 ミリ秒の速度を持つコンピューター B。サイズ 300 のインスタンス。

アルゴリズム A がコンピューター A でこのインスタンスを解決するのにかかる時間と、コンピューター B でかかる時間を調べたいと考えています。

私がやりたいのは、n に対してサブ 300 であるため、50*(300^2) = 4500000 になります。

次に、最初のコンピューターの場合は 1 を掛け、2 番目のコンピューターの場合は 2 を掛けます。

これは私には奇妙に感じますが、「実行時間」が 50n^3 であり、「演算回数が 50n^3」ではないため、時間を掛けているような気がします。ミリ秒の二乗の単位になってしまいますが、これはまったく正しくないようです。

私が正しいかどうか、そうでない場合は、質問が実際に何を意味するかを知りたいです。

Answer 1

O（n ^ 3）がある場合は意味がありませんが、例では大きなO表記を使用していません。つまり、O（n ^ 3）があれば、アルゴリズムの複雑さはわかりますが、言ったように正確な演算数はわかりません。

代わりに、実行された操作の正確な数が与えられているように見えます。（それが明示的に述べられていないことを知っていても）。したがって、nを置き換えることは理にかなっています。

Big O表記は、入力のサイズが実行時間またはメモリ使用量にどのように影響するかを示します。しかし、Big Oでは、各操作の速度を考慮しても、正確な実行時間を推測することはできませんでした。

（私が上で説明したように）あなたの答えがとても単純に見える理由の説明を置くことも安全な方法でしょう。しかし、それがなくても、あなたは質問の点数を得ると確信しています。

Answer 2

さて、最近のほとんどのコンピューターでこのように時間がかかることを理解することの無意味さは別として、組み込みシステムでは何らかの意味があるかもしれませんが、それはあなたがしたように私には正しく見えます。

アルゴリズムが何かを完了するために50n^3の操作を必要とする場合、nは処理する要素の数であり、nを300に置き換えると、時間単位ではなく、実行する操作の数がわかります。

したがって、操作ごとの時間を掛けると、必要な時間が得られます。

私には正しく見えます。

Answer 3

50 * n ^ 3のデータは「実行時間」と呼ばれますが、これは、速度評価に使用されるモデルが、それぞれが1時間単位を要するいくつかの基本操作を備えたマシンを想定しているためです。

この場合、アルゴリズムの実行には50 * 500^3時間単位がかかります。コンピューターAでは各時間単位は1ミリ秒、コンピューターBでは2ミリ秒です。

これがユニットに何らかの意味を与えることを願っています、
アサフ。