共 3 篇相关文章
这篇讲的是算法分析中一个关键但常被绕开的数学工具：如何用特征方程法，系统地求解递推关系式。文章作者直接切入，以经典的汉诺塔问题 T(n) = 2T(n-1) + 1 为例，演示了如何将这个递推式转化为封闭形式 T(n) = 2ⁿ - 1 的完整代数过程。 这种技巧是理解递归算法（如分治法）真实复杂度的基石。它超越了仅靠“主定理”快速查表的层面，让你能亲手推导并理解那些复杂度结论的由来。文章不仅给出了步骤，更重要的是展现了从递归定义到显式公式的逻辑链条，让你在遇到新的递推关系时，能有章可循地求解，而不仅仅是猜测或依赖现成结论。 对于需要分析自定义算法复杂度，或想更深入理解算法导论中数学原理的开发者来说，这篇文章提供了一套清晰、可操作的代数解法框架。
这篇讲的是如何用更严谨的数学方法来计算算法的时间复杂度。通常大家习惯直接保留函数中的最高次项，比如将 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)。 这篇内容为理解算法效率提供了一个更坚实的数学视角，帮助开发者不仅知其然，更知其所以然。
这篇讲的是一个经典的几何问题：面对一个凹多边形，如果我们反复地将凹进去的部分“翻出来”（即用一条边替换掉导致凹陷的相邻边，形成新的多边形），是否总能最终得到一个凸多边形？ 文章并非简单地给出结论，而是沿着一条清晰的证明思路展开。作者从多边形内角和与外角和的性质出发，定义了一个衡量多边形“凹凸性”的量。通过分析每一次“翻凹”操作如何必然减少这个量，最终证明了只要操作可以持续进行（即多边形始终不自交），这个过程必定能在有限步内终止，从而得到一个凸多边形。 证明的巧妙之处在于，它将一个直观的几何操作，转化为一个严格的、单调递减的代数论证。文章最后也指出了问题的边界：在实际操作中，如何保证“翻”的过程不会导致边相交，这才是算法实现需要解决的工程问题。
