2

私はコンピュータサイエンスの学生であり、アルゴリズムは初めてです。クラスでアルゴリズムの設計と分析のコースを学んでいます。O(n)アルゴリズムの時間計算量がO(log n)秒などで測定され、実際の時間を秒やミリ秒で測定されない理由を知りたいの ですが。

4

4 に答える 4

3

漸近計算の複雑さは、アルゴリズムの理論的側面を議論するのに役立ちます。実際の実行時間を議論しない主な理由は次のとおりです。

  • 実際の実行時間は、ハードウェア、入力サイズ、および最適化によって大きく異なります。
  • これにより、実行時間が長い（または無限の）アルゴリズムについて話し合い、分析することができます。
  • クラスの分類は、Big-O表記とも呼ばれ、十分な長さの入力が与えられた場合、実装に関係なく、アルゴリズムの効率をわかりやすく説明します。たとえば、O(log(n))アルゴリズムはO(n)十分に長い入力のアルゴリズムよりも高速ですが、入力が短い場合は後者の方が高速になる可能性があります。
  • この議論は言語にとらわれず、あらゆるソフトウェアアーキテクチャに当てはまります。

実用的な考慮事項は常に考慮に入れる必要がありますが、Big-Oはアルゴリズムソリューションに関するすべての議論の基礎です。Big-Oでアルゴリズムを分析できない場合、コードはスケーリングされません。

于 2013-02-21T09:37:29.717 に答える
3

効率が実際の時間で秒/ミリ秒で表されないのはなぜですか？

私たちがそれをしない理由はたくさんあります（そのうちのいくつかは明白です）：

  • 実際の時間は、アルゴリズムの実装によって異なります。
  • 実際の時間は、コンパイラーによって生成されたコード（および指定されたすべての最適化オプション）によって異なります。
  • 実際の時間は、タイムシェアリング、通信オーバーヘッド（分散アルゴリズム）などによって異なります。
  • 実際の時間は、プログラムを実行しているシステムの構成（クロックレート、キャッシュサイズ、ネットワークトポロジなど）によって異なります。
  • また、アルゴリズムが問題のサイズに応じてどのようにスケーリングするかを確認したいと思います。問題のサイズに関してアルゴリズムがどれだけ高速であるかを説明する関数がより便利です。

効率が入力のサイズの正確な関数として記述されておらず、正確な実行時間を与えるのはなぜですか？

  • ここでも、システムの構成（システムアーキテクチャ、クロックレート、命令セットなど）
  • 繰り返しになりますが、コードに対するコンパイラーによる最適化により、係数の一部が変更される場合があります。
  • 複雑なアルゴリズム、または正確な実行時間が出力のいくつかの特性に依存するアルゴリズムの正確な式を導出するのは簡単ではない場合があります。

それで？

そのため、関数のクラスに属すると説明されています。

そうすることの利点は、実装や実際のシステムの詳細に深く踏み込む必要なしに、（入力サイズに関して）アルゴリズムのスケーラビリティについて知っていることです。アルゴリズムのクラスの最良/最悪の時間計算量を説明することもできます（たとえば、比較ベースのソートアルゴリズムの場合はOmega（n log n））。

そうすることの不利な点は、定数が隠され、最も強力な用語だけが残ることです。2つのアルゴリズムは同じ時間計算量を持つ可能性がありますが、定数が小さいため、一方が他方よりも高速である可能性があります（フロイドサイクル検出アルゴリズムとブレントサイクル検出アルゴリズム）。巨大な隠れ定数を持つ一部のアルゴリズムは、入力サイズが非常に大きい場合にのみ役立ちます。したがって、時間計算量だけに基づいてアルゴリズムを選択するのではなく、許容可能な最大入力サイズを考慮する必要があります。

于 2013-02-21T10:00:46.027 に答える
2

単一の命令を実行する時間はハードウェアに依存し、アルゴリズムは人間が作成したものであるため、その特定の形式で回答を返すことが推奨されます。Big Oは、最悪の場合を定義します。Nは、ブロックコードが実行される回数を表します。ここで、nは通常、配列オブジェクトの要素の数を定義します。

于 2013-02-21T09:40:34.393 に答える
1

理解しておくべき重要なことは、これらの複雑さのクラスは、アルゴリズムの実際の実行時間を記述するために設計されているのではなく、最悪の場合の実行時間を記述するように設計されているということです。

再帰的で複雑度クラスO（2 ^ N）のアルゴリズムは、渡されたパラメーターのために実際に再帰を実行する必要がない場合、O（1）と同等に実行される可能性があるため、これは重要です。アルゴリズムの特定の実行を記述していないBig-O表記-繰り返しますが、アルゴリズムの最悪の場合の実行を記述しています。

実行時間のミリ秒測定は、別のことを測定します。Big-O表記は、上記のアルゴリズムの最悪のケースを説明しますが、ミリ秒の時間測定では単一の特定のマシンでの単一の特定の実行しか説明できないのに対し、それは実行中の特定のプラットフォームに固有ではない方法で説明します。平均的なデスクトップシステムでは、特にC＃.NETやJavaなどの管理された言語で構築している場合、ガベージコレクションなどのアルゴリズムを実行するたびに変動を引き起こす可能性があります-関数の実行にかかる時間を測定しますある瞬間は3ミリ秒、次の1分間は5ミリ秒になる場合があります。より高速なコンピュータでは、0.005ミリ秒しかかからない場合があります-ご覧のとおり、

于 2013-02-21T09:50:42.953 に答える