算法导论课后题

2.3-4 We can express insertion sort as a recursive procedure as follows. In order to sort $A[1..n]$, we recursively sort $A[1..n-1]$ and then insert $A[n]$ into the sorted array $A[1..n-1]$. Write a recurrence for the running time of this recursive version of insertion sort.

\[T(n) = \begin{cases} \Theta(1) & \text{if } n = 1, \\ T(n-1) + C(n-1) & \text{otherwise}. \end{cases}\]

where $C(n)$ is the time to insert an element in a sorted array of $n$ elements.

1. \[若有f(n)=a_mn^m+a_{m-1}n^{m-1}+···+a_1n^1+a_0 (a_m>0),是否有f(n)=O(n^m)\]
2. \[若有f(n)如上，是否同样有f(n)=O(n^{m+e}) (e>0)\]

\[已知Strassen的矩阵相乘的递归算法中，运行时间为\Theta (n^{lg7});且2.80< lg7 < 2.81\] \[为何同样也可以将Strassen的运行时间表示为O(n^{2.81})\] \[按照以上的推论，应该表示为O(n^{lg7})才算严谨，否则不能满足\lim_{n\to\infty}f(n)/g(n)=a (a为非零常数)\]

本文共733字符