我希望你能帮助评估以下算法(以伪代码编写)的复杂性最佳表示方法:
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)))。然而,我必须说,至少95%的输入N不会遇到最坏情况。
通过在满足条件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符号来表示这个算法,我只是想找到某种方式来事实地表示它的平均情况结果,这些结果往往非常好。任何关于至少要探索的方向的见解都将不胜感激。截至目前,我的数学知识远远超过我的计算机科学知识,因此我对这种东西的了解很少。
谢谢, DevenJ