MixedSort（冒泡排序改进版）时间复杂度主定理分析正确性验证

递推式验证 #

首先确认递推式的推导是准确的：

• 基准情况：当n=1时，算法直接返回元素，时间复杂度为O(1)，对应T(1)=1。
• 递归情况：
  • 前半部分调用冒泡排序：冒泡排序时间复杂度为O(m²)，其中m=n/2，代入得O((n/2)²)=O(n²)。
  • 递归处理后半部分：时间复杂度为T(n/2)。
  • 合并两个有序数组：时间复杂度为O(n)，和主导项*O(n²)*相比可忽略不计。
    因此递推式简化为T(n) = T(n/2) + O(n²)，和你推导的一致。

主定理应用验证 #

主定理的通用形式为T(n) = aT(n/b) + f(n)，对应到本题：

• a=1（每次递归仅调用1个子问题）
• b=2（子问题规模为原问题的1/2）
• f(n)=n²

计算对数项：log_b a = log₂1 = 0。
由于f(n)=n²满足f(n) = Ω(n^(0+ε))（取ε=2>0），且满足正则条件：对于足够大的n，a*f(n/b) = f(n/2) = (n/2)² = n²/4 ≤ c*f(n)（取c=1/2<1即可），符合主定理的第三种情况，因此T(n) = Θ(f(n)) = Θ(n²)，即时间复杂度为O(n²)。

内容的提问来源于stack exchange，提问作者RainBat