2.4.5 线性对数算法的性能
性能指标很好地描述了同类算法的共同行为。为了更好地阐述算法在实践中的行为，我们定义了一个函数t(n)，用于表示算法解决样本规模为n的问题所需要的时间。分治法是解决问题的一个高效方法，它将规模为n的问题划分成（大致相等的）两个规模为n/2的子问题，并通过递归解决问题。这些子问题会通过线性时间方式合并在一起来解决原先规模为n的问题。使用数学表达式可以表示为：
也就是说，t(n)包括了解决两个子问题和归并结果的费用，其中归并结果的费用不超过线性时间（即c*n）。在等式的右边，t(n/2)是解决规模为n/2 的问题的时间，按此逻辑推理，t(n/2)可以表示为：
所以最初的等式可以写为：
如果再扩展一层，可以得到：
继续阅读与本文标签相同的文章
-
5G远程驾驶和微公交首秀互联网大会
2026-05-14栏目： 教程
-
学宏程序编程，这些知识必不可少！
2026-05-14栏目： 教程
-
华为准备卖出“落后”的5G，多家美企极力竞争！任正非格局太大！
2026-05-14栏目： 教程
-
百度：飞桨深度学习平台已累计服务150多万开发者
2026-05-14栏目： 教程
-
滴滴公布安全功能数据：近2亿用户添加紧急联系人
2026-05-14栏目： 教程