-1

n と x に依存する特定のアルゴリズムの実行時間 O(n, x) = Theta(n, x) を大量 (> 100) の例 (アルゴリズムが n と x にかかる時間) で計算したい）。実際にこれを行う方法はありますか？

n と x (!) が増加すると実行時間が増加することはわかっていますが、n または x mac は n ^ x のように増加するため、コヒーレンスが複雑すぎて「手」で O(n, x) を把握できないと思います。さらに悪い。

ところで。この問題を解決するために私が最も好む言語は、Python または PHP です。

4

2 に答える 2

2

Eureqaと呼ばれる無料のツールに興味があるかもしれません。データを与えると、データに適合する方程式の候補が見つかります。たとえば、さまざまな入力サイズでアルゴを実行し、それぞれの実行時間を記録してから、このデータを Eureqa に渡します。その後、データに適合する数式が表示されます。

多くのアルゴリズムの実行時間は、入力データの特定の値に大きく依存します。このため、データがアルゴリズムを限界まで押し上げているかどうかがわからないため、これは漸近分析を行うために使用する優れた方法であるとは限りません。

しかし、私たちは目的を達成するための手段として漸近分析を使用します。多くの場合、実世界のデータに対して実世界でうまく機能するアルゴリズムを選択したいと考えています。これはベンチマークのようなものですが、素晴らしい追加の数学的洞察が得られます。また、漸近分析自体は、有用なほど単純な答えを得るために単純化して期待値を下げる必要があるという事実への譲歩であることを覚えておいてください。

彼らの YouTube ビデオをご覧ください http://www.youtube.com/watch?v=NhC1Qb-PQ5Q

于 2012-11-25T17:52:46.293 に答える
1

最善の方法は、アルゴリズムを詳しく調べ、各ステップを分析して、平均および最悪の場合のランタイム クラスを計算することです。

それが不可能な場合は、比較的小さい数値でアルゴリズムを実行し、それらを互いに比較できます。ランタイムがいずれかのパラメーターの順序で指数関数的である場合、10 または 20 の違いがあっても、それは露骨に明らかなはずです。単にランタイムをプロットすると、

  • x = 10 および範囲内の y(50)
  • y = 10 および範囲内の x (50)
  • 範囲内の x (50)、y=x

大まかなアイデアが得られるはずです。ランタイムが大きくなったとき、たとえば のランタイムの 10000 倍を超えたときに、早期に中止できます(1,1)。

これで大まかな見積もりが得られるはずですが、正確ではなく (テスト データが誤って特定のパターンに従い、適切なケースにヒットする可能性があります)、十分でもないことを十分に認識しておく必要があります (関連する要因は非常に小さい可能性があります。 、言う、x + 0.0001 * 1.05^y)。幸いなことに、多くの場合、指数アルゴリズムの底は 1 よりかなり大きくなります。

Python では、このtimeitモジュールを使用してランタイムを正しく測定できます。

于 2012-11-25T17:42:08.413 に答える