performance - 如何判断一个函数增长的快慢？

Question

您能否按照增长最快到最慢的方式对这些进行排名，并解释原因

1（常数）、log2n（对数）、n（线性）、n * log2 n（“n log n”）、n2（二次）、

标签： performancebig-orank

Answer 1

如果您尝试确定两个函数哪个渐近增长更快，只需计算商的极限。所以对于两个函数f(n)和g(n)计算lim f(n)/g(n)。如果它是无穷大f，增长更快，如果它是零g增长更快，如果结果是别的东西，它们以相同的速度增长。

至少对于所有学校示例，这应该适用于大多数情况，并避免找到“大”数字的问题。在函数的上下文中，数字是否很大并不总是很清楚。例如f(n) = log(n)，g(n) = 2^-20 * n。g比 增长快f，但是f(2^20) = 20和g(2^20) = 1。

在现实生活中需要使用lim sup它，有时甚至更复杂。