big-0 的小增长函数可以被认为更大吗？
Can small growth functions of big-0 be considered larger?
f(n)= 45n+3 等较小的增长函数是否可以被视为 o(2^n) 以及 o(n)
如果 f(n) = o(g(n) 和 g(n) = o(h(n)) 则 f(n) = o(h(n))。
证明：o有不同的定义，但其中一个涉及极限：f(n) = o(g(n))可以定义为lim f(n)/g(n) -> 0等于n -> +inf。假设 f(n) = o(g(n)) 和 g(n) = o(h(n))。然后 lim f(n)/g(n) -> 0 和 lim g(n)/h(n) -> 0。我们可以通过将 top 和 bottom 乘以 g(n) 得到 lim f(n)/h(n) x g(n)/g(n) 来找到 lim f(n)/h(n)。我们可以重新排列它以获得 lim f(n)/g(n) x g(n)/h(n)。当存在极限时，乘积的极限是极限的乘积，而我们两者都存在：lim f(n)/g(n) x g(n)/h(n) = 0 x 0 = 0。所以我们根据需要有 lim f(n)/h(n) = 0，或 f(n) = o(h(n))。
正如所指出的那样，45n + 3 = o(n) 并非您示例中的情况。的确，lim (45n + 3)/n = 45，而不是 0，正如所要求的那样。
我更喜欢 o 的另一个定义：f(n) = o(g(n)) iff for all c > 0 there exists n0 such that for n > n0, f(n) < cg(n)。这更好地显示了与 O 的关系。传递性证明如下：
证明。假设 f(n) = o(g(n)) 和 g(n) = o(h(n))。然后对于所有 c > 0 存在 n0 这样对于所有 n > n0 和对于所有 c' > 0 f(n) < cg(n) 存在 n0' 这样 g(n) < c'h(n) 所有 n > n0'。让n0'' = max(n0, n0')和c'' = cc'。然后 f(n) < cg(n) < cc'h(n) = c''h(n) 为所有 n > n''；因此，f(n) = o(h(n))，随心所欲。
f(n)= 45n+3 等较小的增长函数是否可以被视为 o(2^n) 以及 o(n)
如果 f(n) = o(g(n) 和 g(n) = o(h(n)) 则 f(n) = o(h(n))。
证明：o有不同的定义，但其中一个涉及极限：f(n) = o(g(n))可以定义为lim f(n)/g(n) -> 0等于n -> +inf。假设 f(n) = o(g(n)) 和 g(n) = o(h(n))。然后 lim f(n)/g(n) -> 0 和 lim g(n)/h(n) -> 0。我们可以通过将 top 和 bottom 乘以 g(n) 得到 lim f(n)/h(n) x g(n)/g(n) 来找到 lim f(n)/h(n)。我们可以重新排列它以获得 lim f(n)/g(n) x g(n)/h(n)。当存在极限时，乘积的极限是极限的乘积，而我们两者都存在：lim f(n)/g(n) x g(n)/h(n) = 0 x 0 = 0。所以我们根据需要有 lim f(n)/h(n) = 0，或 f(n) = o(h(n))。
正如所指出的那样，45n + 3 = o(n) 并非您示例中的情况。的确，lim (45n + 3)/n = 45，而不是 0，正如所要求的那样。
我更喜欢 o 的另一个定义：f(n) = o(g(n)) iff for all c > 0 there exists n0 such that for n > n0, f(n) < cg(n)。这更好地显示了与 O 的关系。传递性证明如下：
证明。假设 f(n) = o(g(n)) 和 g(n) = o(h(n))。然后对于所有 c > 0 存在 n0 这样对于所有 n > n0 和对于所有 c' > 0 f(n) < cg(n) 存在 n0' 这样 g(n) < c'h(n) 所有 n > n0'。让n0'' = max(n0, n0')和c'' = cc'。然后 f(n) < cg(n) < cc'h(n) = c''h(n) 为所有 n > n''；因此，f(n) = o(h(n))，随心所欲。