选择排序循环关系

Question

预先这是一道作业题，但我很难理解递推关系。我已经在互联网上搜索了示例，它们对我来说非常模糊。我知道递归算法的递归关系没有一套处理每个关系的方法，但我不知道如何理解这些。这是我必须使用的算法：

void selectionSort(int array[]) {
   sort(array, 0); 
} 

void sort(int[] array, int i) {
   if (i < array.length - 1) 
   { 
      int j = smallest(array, i);    T(n) 
      int temp = array[i]; 
      array[i] = array[j]; 
      array[j] = temp; 
      sort(array, i + 1);    T(n)
   } 
} 

int smallest(int[] array, int j)     T(n - k)
{ 
   if (j == array.length - 1) 
      return array.length - 1; 
   int k = smallest(array, j + 1); 
   return array[j] < array[k] ? j : k; 
}

据我了解，这就是我想出的：T(n) = T(n – 1) +cn + c T(n-1)表示sort的递归函数，加的cn表示smallest的递归函数，随着n的减小应该递减，因为每次只调用数组中剩余的次数。常数乘以 n 是运行最小附加代码的时间量，附加常数是运行排序附加代码的时间量。这是正确的吗？我完全离开了吗？我没有正确解释吗？此外，下一步是从中创建一个递归树，但我不认为这个等式是 T(n) = aT(n/b) + c 的形式，如果我理解的话，这是树所需的形式这个权利。此外，如果它是正确的，我也看不到我的递归关系如何达到 n^2 。这也是我的第一个 post 所以如果我在这里做错了什么，我深表歉意。感谢您的帮助！

Answer 1

计算时间复杂度的最简单方法是使用单独的递推关系对每个函数的时间复杂度建模。

我们可以用递归关系S(n) = S(n-1)+O(1)、S(1)=O(1)对函数smallest的时间复杂度进行建模。这显然解决了 S(n)=O(n).

我们可以用T(n) = T(n-1) + S(n) + O(1)、T(1)=O(1)对sort函数的时间复杂度进行建模。 S(n) 术语的出现是因为我们在函数 sort 中调用了 smallest。因为我们知道 S(n)=O(n) 我们可以写成 T(n) = T(n-1) + O(n)，并且写出递归我们得到 T(n)=O(n)+O(n-1)+...+O(1)=O(n^2).

所以总运行时间是 O(n^2)，正如预期的那样。

Answer 2

在选择排序算法中

我们的外层循环运行了 n- 1 次（n 是数组的长度）所以 n-1 次通过...然后将元素与其他元素进行比较...所以 n-1比较

T(n)=T(n-1) + n-1

可以通过求解特定关系证明为 O(n^2) ..

选择排序循环关系

Selection Sort Recurrence Relation

algorithm

sorting

recursion

time-complexity

recurrence