複雑さの場合...データの実行時間が0.1秒であることがわかっている場合O(nlog2(n))、データの実行時間をどのように証明しますか?10e710e5
1 に答える
1
要するに: 私の知る限り、この方法で証明することはできません。
より冗長に:
複雑さに関する問題は、それらがBig O 表記法で報告され、定数と低次の項が破棄されることです。例えば; 問題の複雑さですが、O(nlog2(n))これは の単純化された形式である可能性がありk1 * n * log(k2 * log(k3 * n + c3) + c2) + c1ます。
これらの定数は、サンプル数に関係なく同じ時間がかかる初期化タスク、ビットを実行するのにかかる比例時間log2(n)(それぞれのタスクが潜在的にビットよりも 10^6 倍長くかかる可能性があるn) などをカバーします。
定数に加えて、アルゴリズムが実行されるハードウェア、システムへの追加負荷などの可変要因もあります。
これを実行時間の見積もりの基礎として使用するには、定数と可変要因の両方を見積もるために、問題のサイズに関して十分な実行時間のサンプルを用意する必要があります。
実用的な目的のために、十分に大きな問題サイズのセットに対して実行時間の複数のサンプルを収集し、複雑さの公式に基づいて適切な関数でデータを適合させることができます。
実行時間を証明するという点では...実際には実行可能ではありませんが、期待できる最善の方法は、最適なモデルと有意なp値です。
もちろん、大まかな推測が必要な場合は、すべての定数と変数が必要に応じて 1 または 0 であると仮定して、あなたが持っている数値を差し込むことができます。(0.1s / (10^5 * log2(10^5))) * (10^7 * log2(10^7)) = 11 ish
于 2015-01-19T22:52:00.227 に答える