1

书中的定义说

“大哦”符号

设 f(n) 和 g(n) 是将非负整数映射到实数的函数。我们说 f(n) 是 O(g(n)) 如果有一个实常数 c > 0 和一个实常数 n0 ≥ 1 使得

f(n) ≤cg(n), for n ≥ n0.

我无法理解公式和定义中使用的术语，有人可以用简单的英语解释。

4

3 回答 3

3

基本上，isf(n)与的最坏情况成正比。O(g(n))g(n)f(x)

例如，二分查找是O(log n)（或O(ln n)，这是等价的）。为什么？

（二分查找是这样工作的：取中间元素，并与目标比较。如果是那个，你就完成了。如果它大于目标，则丢弃列表的后半部分并在前半部分重复；如果它小于目标，则丢弃前半部分并在后半部分重复搜索。）

因为您需要 1 次操作才能在 3 个元素长的列表中找到某些东西；7 个元素时的 2 次操作；3 如果它是 15 个元素长。因此，当元素n数(2^x - 1)为 anyx时，操作数为x；把它转过来，你会说元素n的数量，操作的数量是log_2 n。并假设每个操作持续 2 秒（假设您正在手动比较东西），最糟糕的搜索时间是log_2 n * 2 seconds. log_2 n可以改写为ln n / ln 2，所以公式变为：

worst search time(n) = (ln n / ln 2) * 2 seconds
                     = (2 seconds / ln 2) * ln n

现在，2 seconds / ln 2是一个常数；让我们称之为c。让我们称之为“搜索 n 个元素的时间” f(n)。让我们ln n称之为g(n)。

我们之前说过，如果n = 3，g(3) <= c * ln 3（因为c * ln 3是最坏的搜索时间，实际搜索时间总是小于或等于那个时间；但我们总是可以在第一次尝试时找到它）。如果n = 7, g(7) <= c * ln 7; 等等

关于这一点n0只是一个守卫，它说我们为小的计算的复杂性n可能是偏差，异常，规则的例外，如果我们使用足够大的数据（即n >= n0），规则变得显而易见且不可违反。在这种情况下，该规则从一开始就非常有效，但某些算法可能会产生额外的成本，从而导致对小数字的计算无法进行。

于 2013-07-31T05:45:34.620 回答
1

翻译成“简单的英语”：想象一下 f(n) 是 g(n) 函数，它以正数或零作为输入，并给出一个实数作为输出（没有虚数）。

Big-Oh 允许我们比较两个函数，看看一个是否受另一个约束。例如，指数函数f(n)不会受到线性函数 的限制g(n)，因此f(n)也不会O(g(n))。

我们可以说，f(n)如果O(g(n))以下情况是可能的f(n) ≤ c * g(n) for n ≥ n0：c如果有某种方法可以通过插入和来求解方程n0，那么f(n)就是O(g(n))。

例如（同上），让f(n) = 2^n, g(n) = n. 以下是可以解决的：2^n ≤ c * n for n ≥ n0? 答案是不。无论插入什么值，当接近无穷大c时，左侧总是大于右侧。n对于所有值，没有办法使左侧小于右侧n ≥ n0。

另一方面，如果f(n) = 2n, g(n) = n，则条件为2n ≤ c * n for n ≥ n0。这是可以解决的：c = 2, n0 = 0。

于 2013-07-31T05:30:11.927 回答
0

设 f(n) 和 g(n) 是将非负整数映射到实数的函数。

令f(n)和g(n)是nie domain 的值为 0 或正整数的函数，对于这些值的f(n)和g(n)的值n可以是实数。

我们说 f(n) 是 O(g(n)) 如果有一个实常数 c > 0 和一个实常数 n0 ≥ 1 使得：

f(n) ≤cg(n)，对于 n ≥ n0。

f(n) = O(g(n))如果存在正常数c并且n0对于 所有n >= n0 0 <= f(n) <= cg(n) 。实际上，它意味着渐近小于或等于。f(n)g(n)

例如，考虑f(n) = 3 * n^2 + 5。我们可以通过选择c = 4和n0 = 2来证明f(n)是O(n^2)。这是因为对于所有大于的值：n2

3 * n^2 + 5 <= 4 * n^2

f(n)不是O(n)，因为无论您选择什么常数c和值n0，我总能找到一个n大于的值，n0因此3 * n^2 + 5大于c * n。

于 2013-07-31T05:19:48.677 回答