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-Notation，但（据我了解）最适用于最坏的情况。然而，这个算法很少能满足最坏的情况（如果只满足条件 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 秒左右（在我的机器上），即使步骤不同，但在任何方向上都不一致。这个算法是我为我正在写的一篇论文开发的，所以我不仅愿意用大 O 表示法来表示这个算法，我只想用某种方式来真实地表示它的平均情况结果，这往往是非常很好。任何关于至少要研究的方向的见解都值得赞赏。到目前为止，我的数学知识远远超过了我的 CS 知识，所以我接触这种东西的机会很少。

谢谢，德文杰

4

1 回答 1

4

您的算法可以确定的是：

  • O(1)在最好的情况下，
  • O(sqrt(n))在最坏的情况下。

要找到平均运行时间，您必须在随机输入上运行您的算法，并绘制一个表示运行时间或输入大小函数的步数的图表。然后你平滑你的点以尝试将它们拟合到一个函数中。通过绘制该图，您会发现您的平均时间复杂度可能O(1)也在平均情况下。

于 2012-10-27T21:53:34.783 回答