递归函数时间复杂度求解：是否为O(n²logn)？

先看你给出的伪代码：

def inc(m):
  if m>12:
     return;
  for i in range(1,m):
     //some code
  mergeSort(array,0,n-1)
  for j in range(1,m):
     //some code
  inc(m+=1);

咱们一步步拆解复杂度：

• 递归调用次数是固定常数：这个函数的终止条件是m>12，不管初始调用时m是1还是其他≤12的数，递归最多执行12次（比如从m=1到m=12，第12次调用后m变成13，直接返回），总调用次数是个固定值。
• for循环的开销是常数级：每个for循环执行m-1次，而m最大是12，就算两个循环加起来，单次调用里循环最多执行2*(12-1)=22次，12次递归总共有12*22=264次循环操作——不管n多大，这个数都是固定的，属于O(1)的常数开销，不会主导整体复杂度。
• 归并排序是核心开销：每次递归调用都会执行一次mergeSort(array,0,n-1)，而归并排序的时间复杂度是O(n log n)。因为总共执行12次归并排序，12是常数，所以这部分总开销是12*O(n log n)，也就是O(n log n)。

所以整体时间复杂度是O(n log n)，你猜测的O(n²logn)不对——这里没有和n²相关的操作，for循环的次数是固定的，不会随n增长而变化，完全不影响主导项。

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