书中的定义说
“大哦”符号
设 f(n) 和 g(n) 是将非负整数映射到实数的函数。我们说 f(n) 是 O(g(n)) 如果有一个实常数 c > 0 和一个实常数 n0 ≥ 1 使得
f(n) ≤cg(n), for n ≥ n0.
我无法理解公式和定义中使用的术语,有人可以用简单的英语解释。
书中的定义说
“大哦”符号
设 f(n) 和 g(n) 是将非负整数映射到实数的函数。我们说 f(n) 是 O(g(n)) 如果有一个实常数 c > 0 和一个实常数 n0 ≥ 1 使得
f(n) ≤cg(n), for n ≥ n0.
我无法理解公式和定义中使用的术语,有人可以用简单的英语解释。
基本上,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
),规则变得显而易见且不可违反。在这种情况下,该规则从一开始就非常有效,但某些算法可能会产生额外的成本,从而导致对小数字的计算无法进行。
翻译成“简单的英语”:想象一下 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
。
设 f(n) 和 g(n) 是将非负整数映射到实数的函数。
令f(n)和g(n)是n
ie 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)。这是因为对于所有大于的值:n
2
3 * n^2 + 5 <= 4 * n^2
f(n)不是O(n),因为无论您选择什么常数c
和值n0
,我总能找到一个n
大于的值,n0
因此3 * n^2 + 5大于c * n
。