我正在执行CLRS的算法简介中的练习。这不是定级作业，也不是任何东西，我只是想了解问题。
问题如下：
我们可以将插入排序表示为递归过程，如下所示。为了对A [1..n-1]进行排序，我们递归对A [1..n-1]进行排序，然后将A [n]插入已排序的数组A [1..n-1]。为此插入排序的递归版本的运行时间编写一个递归。
解决问题的方法：
由于在最坏的情况下需要O（n）时间才能将A [n]插入排序后的数组A [1]。.n -1]，如果n = 1，则得到递归T（n）= O（1），如果n> 1，则得到T（n-1）+ O（n）。这种重复的解决方案是T（n）= O（n ^ 2）。
所以我得到如果n = 1，那么它已经被排序，因此需要O（1）时间。但是我不理解重复的第二部分：O（n）部分是我们将要排序的元素插入到数组中的步骤，这需要最坏的情况O（n）时间-在这种情况下，我们必须遍历整个数组并在其末尾插入。
我无法理解它的递归部分（T（n-1））。T（n-1）是否意味着我们对数组的一个较少元素进行排序的每个递归调用？那似乎不对。
是的，它来自：
为了对A [1..n-1]进行排序，我们递归对A [1..n-1]进行排序，然后将A [n]插入已排序的数组A [1..n-1]
“递归排序A [1..n-1]”部分需要T（n-1）时间（这很容易：我们将T（n）定义为表示“对n个元素进行排序所需的时间”，因此对n-1个元素进行排序所需的时间通常为T（n-1）），而“将A [n]插入排序后的数组A [1..n-1]”部分需要（最坏的情况）O（ n）时间。将它们加在一起即可
T（n）= T（n-1）+ O（n）
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句