SupposewehaveT(n)≤c=O(1)foralln≤3,andforeveryn≥4,wehave ,T(n)<=T(n/4)+T(0.75*n)+c*n,Use Mathematical Induction to prove that T (n) = O(n log n) for all n ≥ 4.
时间: 2023-03-13 16:12:10 浏览: 67
证明用数学归纳法: 首先,需要证明T(4)≤c*4 log 4,由于T(4)≤c,所以T(4)≤c*4 log 4。 下面,我们必须证明,对于任意的n≥4,如果T(k)≤c*k log k,那么T(n)≤c*n log n。 由于T(n)≤T(n/4)T(0.75*n)c*n,所以T(n)≤T(n/4)T(0.75*n)c*n,而T(n/4)≤c*(n/4) log (n/4),T(0.75*n)≤c*(0.75*n) log (0.75*n),所以T(n)≤c*(n/4) log (n/4) + c*(0.75*n) log (0.75*n) + c*n,也就是T(n)≤c*n log n,从而证明了T(n)=O(n log n),对于所有的n≥4。
相关问题
SupposewehaveT(n)≤c=O(1)foralln≤3,andforeveryn≥4,wehave ,T(n)<=T(n/4)+T(0.75*n) + c*n,Use Mathematical Induction to prove that T (n) = O(n log n) for all n ≥ 4.
证明:首先,假设T(n)<=c*n,当n=4时,我们有T(4)<=c*4,即T(4)<=O(1);假设T(k)<=c*k*log k,当k>4时,由T(n)<=T(n/4) T(0.75*n)和T(n)<=c*n可得:T(n)<=(c/4)*n*log(n/4)+(3/4)*c*n<=c*n*(log n-log 4+3)<=c*n*log n,即T(n)<=c*n*log n,由归纳法可知T(n)<=c*n*log n 对于所有n >= 4。因此,T(n)=O(n log n) 对于所有n>=4。
SupposewehaveT(n)≤c=O(1)foralln≤3,andforeveryn≥4,wehave ,T(n)<=T(n/4)+T(0.75n*)+cn,Use Mathematical Induction to prove that T (n) = O(n log n) for all n ≥ 4.
用数学归纳法证明T(n)=O(nlogn),可将n分为三种情况。首先,当n=4时,T(n)≤T(1)=c=O(1),由假设可知T(n)<=T(n/4) T(0.75n*) cn,故T(4)≤T(1) T(3) T(3) c4,即T(4)≤c4,即T(4)=O(4),证明了当n=4时T(n)=O(n)。其次,假设当n=k时T(k)=O(k)成立,即T(k)≤ck,则当n=k+1时T(k+1)≤T(k/4)T(3k/4)T(3k/4)ck+1,即T(k+1)≤ck+1,即T(k+1)=O(k+1),证明了当n=k+1时T(n)=O(n)。最后,由数学归纳法可知,当n≥4时,T(n)=O(nlogn)。
相关推荐
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)