算法时间复杂度计算求助：SortRight递归算法执行次数分析及思路指导

我正尝试计算SortRight递归算法的时间复杂度，但难以理解各代码行的执行次数，希望获得此类问题的分析思路指导，而非仅针对该算法的解答。

给出的算法代码： #

int SortRight(A, i) {
n= len(A);
if (i == n-1) return A;
for (j= (i + 1); j < n; j++) {
if (A[i] < A[j]) { temp= A[i]; A[i]= A[j]; A[j]= temp; } }
  return SortRight(A, i+1)
}

我自行标注的各代码行执行次数（不确定是否正确）： #

int SortRight(A, i) { //n+1
n= len(A); //n+1
if (i == n-1) //n+1
{return A;} //1
for (j= (i + 1); j < n; j++) { // (1) n*(n-1)
if (A[i] < A[j]) { temp= A[i]; A[i]= A[j]; A[j]= temp; } } // 不清楚这部分的执行次数
  return SortRight(A, i+1)
}

我的分析(1)： #

假设当j>=n时，i=k，即j=k+1 => k+1=n，k=n-1。递归调用执行n次，因此这部分执行n*(n-1)次。

通用分析思路 #

1. 先确定递归调用的总次数 #

递归函数的调用次数由终止条件决定。以SortRight为例，初始调用是SortRight(A, 0)，每次递归i加1，直到i == n-1时终止，因此总调用次数是n次（i取0到n-1）。

2. 拆解单次递归的执行成本 #

对每一次递归调用，拆分不同语句的执行次数：

• 固定执行的语句：比如n=len(A)、if(i == n-1)这类非循环、非递归的语句，每次调用都执行1次，总次数就是递归调用次数×1，也就是n次（你标注的n+1是把终止时的额外判断算进去，实际递归调用n次，这些语句就执行n次）。
• 循环语句：要找到循环迭代次数和当前递归参数的关系。比如SortRight里的for循环，当当前递归参数是i时，j从i+1遍历到n-1，迭代次数是n - i - 1次。把所有递归调用的循环次数累加：

  当i=0时：n-1次
  i=1时：n-2次
  ...
  i=n-2时：1次
  

  总和是(n-1)+(n-2)+...+1 = n(n-1)/2，这才是循环的总执行次数，不是你标注的n*(n-1)。

3. 区分条件执行语句的情况 #

像代码里的交换语句，只有满足A[i]<A[j]时才执行，这时候要分三种情况分析：

• 最坏情况：数组是升序排列，每次比较都满足条件，交换语句每次循环都执行，总次数等于循环总次数n(n-1)/2。
• 最好情况：数组已经是降序排列，每次比较都不满足，交换语句执行0次。
• 平均情况：假设元素随机分布，每次比较满足条件的概率是1/2，交换语句总次数约为n(n-1)/4。

4. 推导时间复杂度 #

时间复杂度只关注最高阶的项，忽略常数和低阶项。不管交换语句执行多少次，这个算法的核心操作（比较+可能的交换）的总次数是O(n²)，因此时间复杂度为O(n²)。

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