いくつかのコードがあり、計算の複雑さがいくつかの（代数的）上限を観察することが重要であるとします。
たとえば、適切に実装された場合は n^2 で実行されるアルゴリズムがあるかもしれませんが、バグが導入された場合は n^3 で実行されます。このテストでは、メソッドが実際に n^2 で実行されているかどうかを確認し、そうでない場合は失敗します。
私の質問は、MSTest でこれを達成することは可能ですか?
一連の数学的コードを導入した後、原則として、与えられた方程式を経験的測定に適合させたり、限界を見つけようとしたりすることが可能であることがわかります。
別の方法として、最適なグラフを作成し、テストに合格するかどうかについて人間に入力を求めることも可能だと思います。
しかし、これらのいずれかが実際に現実的ですか? これまでに同様のことが行われたことがありますか？
実用的な目的でそのようなテストを実施することは不可能な場合があります。数学的分析のみを使用して 2 つのアルゴリズムを比較しようとすると、結果が実用的な目的に役立たない場合があります。たとえば、常にO(n 3 )アルゴリズムよりもO(n 2 )を好むとは限りません。隠れ定数を考慮する必要があります。たとえば、O(1000000 n 2 ) のアルゴリズムは、数学的な観点では依然として O(n 2 ) です。しかし、このようなアルゴリズムは、n の値が 100000 を超えるまで、数学的に O(n 3 ) である O(10 n 3 ) アルゴリズムよりもうまく機能しません。しかし、多くの場合、この制限よりもはるかに小さい入力サイズを処理することがあります。
まず第一に、実行された操作の数を測定できるように、コードを計測できる必要があります。たとえば、並べ替えアルゴリズムをテストしている場合、比較関数が呼び出されるたびにカウンターをインクリメントできます。問題の演算が整数の乗算である場合のように、他のケースでは、これは簡単ではないかもしれません。
次に、「O(n^2)」が何を表すかという問題があります。一部のアルゴリズムでは、最良、最悪、および平均的なケースの複雑さが異なります。それがあなたに当てはまる場合は、どの入力がそれらの各状況につながるかを知り、それらを個別にテストする必要があります.
テストしたいのは、ランタイムが O(n^2) であるということである場合、検証が困難になります。ご存じのように、big-O は漸近的な複雑さについて話しているため、非常に長いテストを実行する必要があります。曲線フィッティングを行って、ax^2 で適切に近似されているかどうかを確認するとします。x > 100 の場合、操作の数が常に 4x^2 を下回る必要があることを知っている場合のように、実際の複雑さを厳密に制限できればより良いように思われます。見積もりを下回っているかどうかを確認します。もちろん、これは、ビッグオーの複雑さを同じままにして係数を変更する変更のためにテストを更新する必要があるかもしれないことを意味しますが、正直なところ、それは良いことのように思えます。