O 符号代数
O notation algebra
我需要证明 (N + 1)(Hn + 0(1)) = NlnN + O(N)。
之前用的Hn = lnN + O(1)的近似。
只是通过扩展它。
= N(lnN + O(1)) + O(N) + (lnN + O(1)) + O(1)
= NlnN + O(N) + O(N) + lnN + O(1) + O(1)
我们忽略额外的 O(N) 和常量 运行 次
但是 lnN 会发生什么，是因为它渐近地小于 NlnN 所以我们可以忽略它吗？
不知道我的理解是否完全错误。
唯一需要证明的就是O(N) + lnN = O(N)。这应该很容易——线性函数比对数增长得更快。就用big-O的定义来证明吧。
您可能已经定义了一个复杂度为 classes 的代数，并且知道 +、* 和 = 的含义，在这种情况下，这只是应用公理（或简单定理）的问题这个代数，但如果不是，你必须更加小心他们的意思，否则你的证明并不可靠。
(N+1)(H(N) + O(1)) 是形式为 (N+1)(H(N) + f(N) 的函数的 class ) 其中 f 是 O(1)，NlnN + O(N) 是形式为 NlnN + g(N) 的函数的 class，其中 g 是 O(N)。等号是class等价。你可以通过说第一个 class 是第二个 class 的子集来证明它，反之亦然。
无论如何，现在我们实际证明的内容更清楚了，我们可以继续了。我将证明等价的一个方向，然后让你做（稍微难一点）相反的方向。
假设我们有一个形式为 (N+1)(H(N) + f(N)) 的函数，其中 f 是 O(1)。
然后有一个 C，使得对于大 N，(N+1)(H(N) + f(N)) <= (N+1)(H(N)+C)。
类似地，有一个 D 对于大 N，H(N) <= lnN + D。将这两个放在一起，对于大 N，我们有 (N+1)(H(N) + F(N)) <= (N+1)(lnN + E)（其中 E=C+D）。
这等于NlnN + lnN+ (N+1)E。由于 lnN + (N+1)E 是 O(N)，我们已经证明我们的函数在 NlnN + O(N) 中。因此 (N+1)(H(N)+O(1)) 是 NlnN + O(N) 的子集。
我需要证明 (N + 1)(Hn + 0(1)) = NlnN + O(N)。
之前用的Hn = lnN + O(1)的近似。 只是通过扩展它。
= N(lnN + O(1)) + O(N) + (lnN + O(1)) + O(1)
= NlnN + O(N) + O(N) + lnN + O(1) + O(1)
我们忽略额外的 O(N) 和常量 运行 次 但是 lnN 会发生什么，是因为它渐近地小于 NlnN 所以我们可以忽略它吗？ 不知道我的理解是否完全错误。
唯一需要证明的就是O(N) + lnN = O(N)。这应该很容易——线性函数比对数增长得更快。就用big-O的定义来证明吧。
您可能已经定义了一个复杂度为 classes 的代数，并且知道 +、* 和 = 的含义，在这种情况下，这只是应用公理（或简单定理）的问题这个代数，但如果不是，你必须更加小心他们的意思，否则你的证明并不可靠。
(N+1)(H(N) + O(1)) 是形式为 (N+1)(H(N) + f(N) 的函数的 class ) 其中 f 是 O(1)，NlnN + O(N) 是形式为 NlnN + g(N) 的函数的 class，其中 g 是 O(N)。等号是class等价。你可以通过说第一个 class 是第二个 class 的子集来证明它，反之亦然。
无论如何，现在我们实际证明的内容更清楚了，我们可以继续了。我将证明等价的一个方向，然后让你做（稍微难一点）相反的方向。
假设我们有一个形式为 (N+1)(H(N) + f(N)) 的函数，其中 f 是 O(1)。
然后有一个 C，使得对于大 N，(N+1)(H(N) + f(N)) <= (N+1)(H(N)+C)。 类似地，有一个 D 对于大 N，H(N) <= lnN + D。将这两个放在一起，对于大 N，我们有 (N+1)(H(N) + F(N)) <= (N+1)(lnN + E)（其中 E=C+D）。
这等于NlnN + lnN+ (N+1)E。由于 lnN + (N+1)E 是 O(N)，我们已经证明我们的函数在 NlnN + O(N) 中。因此 (N+1)(H(N)+O(1)) 是 NlnN + O(N) 的子集。