[理工] [資結] 時間複雜度

[woncho ( )]

1. True or False

2^n = o(2^n)，答案是true

我的想法是
因為o的定義是：對所有c>0，存在n0>0，使得n≧n0時，f(n) < cg(n)

那我找 c = 1，2^n < c˙2^n 這條式子不是就不成立了嗎？

請問為什麼是true？

2. f(n) = f(n-1) + f(n-2) , g(n) = n! , f(n) = Ω(g(n))

   請問f(n)的複雜度怎麼算？

3. 求 T(n) = T(n/2) + 1 的時間複雜度

4. 求 T(n) = 2T(√n) + log n 的時間複雜度

以上幾題還請各位不吝指教，謝謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.136.246.53
推 littlewanzz:1.是只要有存在C跟n0可使上面式子成立就行囉
推 soldier723:1.存在n0>0，使得n≧n0 <= 在想一下就知道了
→ soldier723:3.4.展開帶入 或是 MM去解就是答案了
→ woncho:1.是little o要對所有c都符合，s大可以舉個例子嗎>"<
推 gsrr:第一題我認為是false,Big O對,little o應該不對
→ gsrr:第2題就是Fibonacci number,為O(2^n)
→ gsrr:第3題為binary search,O(logn)
→ gsrr:第4題用變數代換,沒記錯應該是O(logn*loglogn)
推 FRAXIS:第一題應該是false吧..
→ woncho:感謝樓上，我也覺得是FALSE，那應該就是答案錯了，謝謝。
推 soldier723:是False沒錯 :)