"relevant operations"算法分析有哪些？

Question

我一直在研究算法分析，并且多次遇到这样的想法，即要定义算法的时间复杂度，我必须找到该算法执行的 "relevant operations" 的次数。然而，至少据我所知，没有一个来源（Cormen、Skiena、Sedgewick……）提到我如何知道哪些操作实际上是相关的。有帮助吗？

Answer 1

一般来说，您只需计算给定上下文中您关心的操作。

例如

fib(n)
{
   if(n < 2) 
      return 1;

   return fib(n-1) + fib(n-2)
}

您可以在这段代码中找到的操作是：

• if 语句
• 比较
• return一个值
• 递归调用
• 加法

每个操作都需要一些时间来执行，但每个操作执行得非常快（假设输入 n 是一个 64 位数字并且程序 运行s 在 "normal" 电脑）。因此，此函数的复杂性必须来自递归调用，尤其不是来自调用它自身，而是来自调用次数。所以你计算递归调用而忘记其他操作，知道它们 运行 快，意味着 O(1) （恒定时间）。

之所以可以忽略某些操作，是因为您根据o、O、Θ、Ω或[=17来计算复杂度=] (Landau-Notation)，它允许您在渐近方程中进行计算，其中 slwo 增长部分和常数不起任何作用。

我认为没有简单的答案如何知道什么操作是相关的。有一些简单的例子（比如我给的那个），但总的来说并不那么容易。然后你必须计算所有可能相关的东西，直到你注意到它不是。