実行時からBig Thetaを計算しますか？

Question

私は4つの.txtファイルのミリ秒でランタイムを計算するプログラムを持っています。私はロードのランタイムがシータの点で何であるかを計算し、nが何を参照するかを指定しなければなりません。しかし、私はまだ大きなシータ記号表記や漸近表記を全く理解していません。誰も私にいくつかのポインタを与えることができますか？これらのファイルのためのランタイムた：

file1を18000ms

FILE2 48514ms

FILE3 121473ms

FILE4 622446ms

Answer 1

をロードする

ファイルの時間への一般的な方法はありませんプログラムの実行時に経験的ランタイムからシータバンドを導出する。病理学的に最悪の場合（たとえば、線形プログラミングのシンプレックスアルゴリズムが入力の狭いクラスで指数関数的な最悪ケース時間に低下する）など、見た目には分かっていない入力があるかもしれません。長期的な継続を見ている。

経験的にの計算量を派生させたい場合は、データを取ってログ/ログ軸にプロットし、最適なラインを探すのが妥当な解決策です。これが働く理由は、ログ/ログプロット上の直線が多項式フィットに対応するため、これはあなたが持つデータに最も適合する多項式を見つけることになります。あなたの答えがあなたが提供するデータと同じくらい良いことを覚えている限り、これは複雑さをはるかに上回る素晴らしい方法です。