渐近复杂度比较
Asymptotic Complexity comparison
任何人都可以解释其中哪一个具有最高的渐近复杂度以及为什么，
10000000n vs 1.000001^n vs n^2
计算渐近时间复杂度时，需要忽略n的所有系数，只关注其指数。
指数越高，时间复杂度越高。
在这种情况下
我们忽略n的系数，留下n^2, x^n and n.
但是，我们忽略第二个，因为它的指数为 n。由于 n^2 高于 n，所以你的问题的答案是 n^2。
您可以使用 asymptotic analysis 中的标准支配规则。
统治规则告诉你，当n -> +Inf，n = o(n^2)。 （注意符号 O(.) 和 o(.) 之间的区别，后者的意思是 f(n) = o(g(n)) 当且仅当存在一个序列 e(n) 收敛到 0 作为 n -> +Inf 这样 f(n) = e(n)g(n)。对于 f(n) = n、g(n) = n^2，您可以将 f(n)/g(n) = 1/n -> 0 视为 n -> +Inf。）
此外，您知道对于任何整数 k 和实数 x > 1，我们有 n^k/x^n -> 0 作为 n -> +Inf。 x^n（指数）复杂度支配 n^k（多项式）复杂度。
因此，按照复杂性递增的顺序，您有：
n << n^2 << 1.000001^n
注意：10000000n 可以写成 O(n) 与 松散 用于计算机科学渐近分析的书面约定。回想一下，算法的复杂性 C(n) 是 O(n) (C(n) = O(n)) 当且仅当 (iff) 存在整数 p >= 0 和 K >= 0 使得对于所有 n >= p 关系 |C(n)| <= K.n 成立。
任何人都可以解释其中哪一个具有最高的渐近复杂度以及为什么，
10000000n vs 1.000001^n vs n^2
计算渐近时间复杂度时，需要忽略n的所有系数，只关注其指数。
指数越高，时间复杂度越高。
在这种情况下
我们忽略n的系数，留下n^2, x^n and n.
但是，我们忽略第二个，因为它的指数为 n。由于 n^2 高于 n，所以你的问题的答案是 n^2。
您可以使用 asymptotic analysis 中的标准支配规则。
统治规则告诉你，当n -> +Inf，n = o(n^2)。 （注意符号 O(.) 和 o(.) 之间的区别，后者的意思是 f(n) = o(g(n)) 当且仅当存在一个序列 e(n) 收敛到 0 作为 n -> +Inf 这样 f(n) = e(n)g(n)。对于 f(n) = n、g(n) = n^2，您可以将 f(n)/g(n) = 1/n -> 0 视为 n -> +Inf。）
此外，您知道对于任何整数 k 和实数 x > 1，我们有 n^k/x^n -> 0 作为 n -> +Inf。 x^n（指数）复杂度支配 n^k（多项式）复杂度。
因此，按照复杂性递增的顺序，您有：
n << n^2 << 1.000001^n
注意：10000000n 可以写成 O(n) 与 松散 用于计算机科学渐近分析的书面约定。回想一下，算法的复杂性 C(n) 是 O(n) (C(n) = O(n)) 当且仅当 (iff) 存在整数 p >= 0 和 K >= 0 使得对于所有 n >= p 关系 |C(n)| <= K.n 成立。