f（n）

Question

我一直在阅读本教程按时复杂性，我对其对大 $ o $ 表示法的说明感到困惑。它写道：

$ o（g（n））= $ { $ f（n）$ ：在那里存在正常量 $ c $ 和 $ n_0 $ 这样 $ 0 \ leq f（n）\ leq c * g（n）$ 所有 $ n> n_0 $ 。

我理解的方式， $ c * g（n）$ 表示 $ c $ 乘以by $ g（n）$ 。如果是这种情况，那么上述表达式如何指定时间，而不仅仅是 $ c * g（n）$ 大于 $ f（n）$ ？或者我是不正确的，这是一些符号，我不明白？我对时间复杂性的理解是非常基本的，所以如果这只是我的愚蠢错误，请原谅我。

Answer 1

f（n）

它没有。 Bachmann-Landau符号只是一种比较功能增长率的方便方式。它没有说出任何关于这些职能意味着的东西，我们可以很确定在1894年提出它时，Bachmann没有考虑计算机。

为您分配给这些功能取决于您。例如，在分析基于比较的排序算法时，我们通常需要 $ n $ 是集合中的元素数和 $ f（n）$ 是比较数量或掉次数，或掉数量的数量，或比较数量和交换数。

还要注意，所有这些都始终相对于机器模型或成本模型。

作为一个非常简单的例子，如果我问你是什么是复制列表的算法最坏情况的步骤复杂性，你会说 $ o（n）$ 。但实际上，正确的答案是“我无法告诉你，因为你没有指定机器型号”。因为例如，在图定机器中，复制列表是 $ o（n ^ 2）$ ，因为对于正在复制的每个元素，TM的头部都有进一步且进一步且进一步地驾驶列表的末尾以写入下一个元素。

Answer 2

说算法的运行时间位于 $ o（g（n））$ 给出，只要您只注意到上限。此外，上限使用常量 $ c $ 和 $ n_0 $ 未知。 所以是的，它是有关运行时间的相当弱的信息。

未指定的常量 $ c $ 可以包含有关算法基本操作的实际成本的信息，可以在运行之间未知和/或可变，但仍然知道花费了一定的时间。未指定的常量 $ n_0 $ 反映给定的绑定指的是输入的大尺寸（或任何参数 $ n $ < / span>代表）。

其他符号用于提供其他类型或有关运行时间的更精确的信息。