3

私は、次のアルゴリズムの複雑さを記すための最良の方法を評価する助けを得たいと思っていました（疑似コードで書かれています）：

Input N;

bool complete = false;

If(N Satisfies Condition A)
{
    K = N/6;
    For(int i = 1; i <= sqrt(K/6) && complete != true; i++)
    {
        If(K Satisfies Condition B based on i)
                  complete = true;
        Else if(K Satisfies Condition C based on i)
                   complete = true;
        Else if(K satisfies Condition D based on i)
                   complete = true;
        Else if(K satisfies Condition E based on i)
        {
               If(K satisfies Condition D based on (i + 1))
               {
                        Change Output;
                        complete = true;
                }
                Else
                        complete = true;
         }
         Else if(K satisfies Condition F based on i)
         {
                change output;
                continue;
         }
     }
}

私は大きなO表記法に精通していますが、それは（私が理解していることから）最悪の場合に最も具体的に当てはまります。ただし、このアルゴリズムがその最悪のシナリオに適合することはめったにありません（条件Fのみが満たされた場合はO（sqrt（N））になります）。入力Nの少なくとも95％を言わなければなりませんが、その最悪のシナリオを満たしていません。

条件Eを満たすためにifステートメントを埋め込むことで、非常に興味深い結果が得られました。条件Eが満たされるとすぐに、プログラムは基本的に完了します。条件Fのいくつかのまれなケースを除いて、定数O（1）に非常によく似ています。

例えば：

N = 11, Time = 0.004 sec, Steps Taken = 0
N = 101, Time = 0.005 sec, Steps Taken = 1
N = 1001, Time = 0.004 sec, Steps Taken = 0
N = 10001, Time = 0.003 sec, Steps Taken = 1
N = 100001, Time = 0.004 sec, Steps Taken = 1

ただし、そこでパターンを探してはいけません。ランダムではるかに大きな値の結果を見てください。

N = 12764787846358441471, Time = 0.007, Steps Taken = 3332
N = 18446744073709551557, Time = 0.005, Steps Taken = 7

ご覧のとおり、ほとんどの場合、（私のマシンでは）約0.006秒近くにとどまり、手順は異なりますが、どの方向でも一貫していません。このアルゴリズムは、私が取り組んでいる論文のために開発したものであるため、このアルゴリズムを表すためにBig O表記法を受け入れるだけでなく、非常に傾向のある平均的な結果を実際に表す方法が必要です。とても良い。少なくとも調査する方向についての洞察はありがたいです。私の数学の知識は、現在の私のCSの知識を大幅に上回っています。そのため、この種の知識への露出は最小限です。

ありがとう、DevenJ

4

1 に答える 1

4

あなたのアルゴリズムについて確かなことはそれが次のとおりであるということです：

  • O(1)最良の場合、
  • O(sqrt(n))最悪の場合。

平均実行時間を見つけるには、ランダムな入力でアルゴリズムを実行し、入力サイズの関数で実行時間またはステップ数を表すグラフを描画する必要があります。次に、ポイントを滑らかにして、関数に適合させようとします。そのグラフを描くことにより、あなたの平均時間計算量はおそらくO(1)平均的な場合にもあることがわかります。

于 2012-10-27T21:53:34.783 に答える