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 = 3g(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 ≥ n0c如果有某种方法可以通过插入和来求解方程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 = 4n0 = 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 回答