数学中的极限思想求时间复杂度
这篇讲的是如何用更严谨的数学方法来计算算法的时间复杂度。通常大家习惯直接保留函数中的最高次项，比如将 T(n) = 2n^5 + 3n^2 - 1 简写为 O(n^5)。文章指出，这种简便做法其实不够严格，其背后的正确依据应当是数学中的极限概念。 作者详细推导了极限判定法：当 n 趋向无穷大时，T(n) 除以某个猜想 f(n) 与一个常数系数的乘积，若结果为一个常数，则 f(n) 就是 T(n) 的时间复杂度。用这个方法重新计算开头的例子，可以严谨地得出 O(n^5) 的结论。 更重要的是，极限思想能解决一些常规方法棘手的对比。比如比较多项式 n^k 和指数 k^n（k 为大于1的常数）的复杂度，直接判断很模糊。文章通过对两边取对数再求极限，清晰地证明 n^k / k^n 的极限为 0，从而得出结论：当 n 足够大时，O(n^k) 的效率远优于 O(k^n)。最后，文章还展示了如何将指数增长的思想应用于分析循环次数，推导出类似 i = i*2 这种模式的时间复杂度为 O(log₂n)。 这篇内容为理解算法效率提供了一个更坚实的数学视角，帮助开发者不仅知其然，更知其所以然。