さまざまな入力サイズでプログラムの実行時間 (CPU 時間) を秒単位で取得しました。CPU 時間と理論上の実行時間を示すグラフを作成したいと考えています (例: O(n³))。
CPU 時間をどのようにスケーリングすればよいですか?
質問する
164 次
1 に答える
2
CPU 時間と BigO 表記は 2 つの異なるものであるため、比較する必要はありません。
BigO 表記の背後にある考え方は、アルゴリズムの効率を測るプラットフォームに依存しない方法を提供するというものです。CPU の速度、負荷などに応じて、異なる CPU で異なるアルゴリズムが異なる時間に実行されます。したがって、CPU は適切な指標ではありません。アルゴリズムの問題は、それが可能な限り効率的に記述されているかどうかです。
ここで BigO 表記の出番です。これは、タスクを完了するために必要な操作の数を測定するものであり、プラットフォームに依存しません。タスクを完了するために必要な操作の数を減らすと、プラットフォームに関係なく、他のすべてが同じであれば、効率が向上します。
したがって、プログラム内の操作の数を数え、そこから BigO の複雑さを導き出します。次に、理論に対してそれを測定できます。
于 2012-12-05T21:10:46.820 に答える