2.4.5 线性对数算法的性能
性能指标很好地描述了同类算法的共同行为。为了更好地阐述算法在实践中的行为，我们定义了一个函数t(n)，用于表示算法解决样本规模为n的问题所需要的时间。分治法是解决问题的一个高效方法，它将规模为n的问题划分成（大致相等的）两个规模为n/2的子问题，并通过递归解决问题。这些子问题会通过线性时间方式合并在一起来解决原先规模为n的问题。使用数学表达式可以表示为：
也就是说，t(n)包括了解决两个子问题和归并结果的费用，其中归并结果的费用不超过线性时间（即c*n）。在等式的右边，t(n/2)是解决规模为n/2 的问题的时间，按此逻辑推理，t(n/2)可以表示为：
所以最初的等式可以写为：
如果再扩展一层，可以得到：
时间： 2024-11-01 11:35:21