漸近式（Big-O表記）以外のアルゴリズムの複雑さ

Question

アルゴリズムを評価するために使用される漸近複雑度（Big-O記法）以外のほとんどのコンセプトは何ですか？

例：

Iは、複雑さO（1）と、FUNC、関数を呼び出し、以下のアルゴリズムを持っていると仮定すると。このアルゴリズムは、複雑さO（N1×N2）を有する。しかし、N1が制限されていることを事前に知っていれば、最悪の場合の複雑さはO（N2×5）であり、O（N2）も定義になります。場合

for i in range(N1): 
    for j in range(N2): 
     func(i,j) 

Iは、複雑さO（1）で再度、関数func2のを使用して、このアルゴリズムの異なる実装に出くわすが、今異なるアウターループ範囲、N3を使用することができます。このアルゴリズムはO（N3×N2）であると予想される。しかし、N3の範囲が[10,50]であることが分かっていれば、最悪の場合の複雑さはO（50×N2）となり、再びO（N2）となります。

for i in range(N3): 
    for j in range(N2): 
     func2(i,j) 

質問：

だから、これは漸近記法は便利ですが、おそらくいくつかのより具体的な例に最適な比較方法ではないことを証明するのは簡単です。これらの2つのアルゴリズムを比較するにはどうすればよいですか？最も一般的に採用されている方法は何ですか？アルゴリズムに必要な反復の数だけを厳密に厳密なメトリックで使用していますか？

推奨される参考資料はありますか？

Answer 1

あなたの質問は非常に大きいです。アルゴリズムの複雑さとメトリックについて読む。

Big-O（Big-Omega、Small-Omega、Thetaなどの他にも多くの小さなものがあります）を使用しなくても、簡単にアルゴリズムを比較することはできませんあなたが欲しいと思われる！主な理由は、測定したいものを最初に明確に定義する必要があり、これは容易ではないということです。一般的に、あなたは細部を望まない。どうして？なぜなら、我々はいつもアルゴリズムを直線的に加速することができることを知っているからです（大雑把に言えば、ここでは関係のない特別なケース）。したがって、乗法定数は関係ありません。

ここで、正確な複雑さと何らかの形で関係する実行時間の予測関数を（最悪の場合も、最悪の場合も、大文字の場合もありません）しかし、そこにも多くの落とし穴や罠があります。たとえば、3n + 45という複雑さを持つ2つのアルゴリズムが同じプラットフォーム上で高速に実行されると考えるかもしれませんが、これは誤りかもしれません！カウントするものを正確に定義しないと、これは誤っている可能性があります。 3nの乗算と他の3nの加算（またはより微妙な混合）を使用し、乗算と加算の実行時間は一般的に同じではありません。最悪の場合、アーキテクチャーはパイプライン、予測などのランタイム最適化を使用する可能性があるため、実行時間が大幅に変更される可能性があります。環境プラットフォームでさえ、深刻な偏見を招き、仮想メモリ、キャッシュ、さまざまなコンパイラの最適化などを考えるかもしれません。

したがって、答えは：あなたが予測したいことに依存します。複雑さの尺度。