【阿摩網站-置頂欄顏色票選問卷】只要填寫就能獲得500Y，結束時間 2024/04/25 11:59:59。 前往查看

教甄◆電腦科專業題庫下載題庫

上一題
6.下列遞迴式的時間複雜度為何?
T(n) =1                   if n<=2 
T(n) = 2T(n/2)+1    if n>2

 
(A) O(log n)
(B)O(log log n)
(C)O(n)
(D) O(nlog n) 。 

答案：C
難度： 困難
3F
Skytree Wang 高二上 (2016/04/28)
不好意思，請教一下，有人可以寫出解題過程嗎？拜託…
4F
騏騏 國三上 (2017/04/13)

當 n <= 2 時，T(n) = 1 為常數時間，時間複雜度為 O(1)

當 n > 2 時

例如 n = 4

T(4) = 2 * T(4/2) +1 

        = 2 * T(2) + 1

        = 2 + 1

        = 3

再例如 n = 10

T(10) = 2 * T(10/2) + 1

= 2 * T(5) + 1

= 2 * ( 2 * T(5/2) + 1) +1

= 2 * ( 2 * T(2) + 1) +1

= 2 * ( 2 * 1 + 1) +1

= 2 * (2 + 1) + 1

= 2 * 3 + 1

= 6 + 1

= 7

處理時間為線性時間，時間複雜度 O(n)


若有錯還請高手不吝指正...


【補充】常見時間複雜度：

常數時間O(1)如：判斷奇偶數

對數時間O(logn)如：二分搜尋

線性時間O(n)如：循序搜尋

線性對數時間O(nlogn)如：快速排序、合併排序（用linked list）

二次時間...


查看完整內容
5F
ntustslhs 小三上 (2019/03/03)

不好意思 看不太懂3F為何最後會導出O(n)
可以請知道解法的大大解答嗎
(自己不管怎麼算都是O(nlogn) TAT


6.下列遞迴式的時間複雜度為何?T(n) =1     &n..-阿摩線上測驗