适合表示该算法的复杂度符号

Question

我希望你能帮助评估以下算法（以伪代码编写）的复杂性最佳表示方法：

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

- DevenJ

Answer 1

你的算法的确定因素是：

• 在最好情况下为O(1)
• 在最坏情况下为O(sqrt(n))

为了找到平均运行时间，你需要在随机输入上运行你的算法并画出一张代表运行时间或步数与输入规模相关的图表。然后你可以平滑你的数据点并尝试将它们拟合到一个函数中。通过绘制这张图，你会发现你的平均时间复杂度可能也是O(1)。

- alestanis

---

非常感谢，我会这样做并试着看看我能得到什么启发。谢谢。 - DevenJ