我正在执行CLRS的算法简介中的练习。这不是定级作业，也不是任何东西，我只是想了解问题。
问题如下:
解决问题的方法:
所以我得到如果n = 1，那么它已经被排序，因此需要O(1)时间。
但是我不明白复发的第二部分:
O(n)部分是将要排序的元素插入到数组中的步骤，这需要最坏的情况O(n)的时间-在这种情况下，我们必须遍历整个数组并在数组的末尾插入。
我在理解它的递归部分(T(n-1))时遇到了麻烦。 T(n-1)意味着我们递归调用的每个数组的排序次数都减少了一个吗？那似乎不对。
最佳答案
是的，它来自:
“递归排序A [1..n-1]”部分需要T(n-1)时间(这很容易:我们在中定义 T(n)表示“对n个元素进行排序所需的时间” ，因此对n-1个元素进行排序所需的时间通常为T(n-1))，而“将A [n]插入已排序的数组A [1..n-1]”部分(最坏的情况)准时。将它们加在一起即可