[理工] [資結]-時間複雜度
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
推
03/19 22:44, , 1F
03/19 22:44, 1F
推
03/19 22:46, , 2F
03/19 22:46, 2F
→
03/19 22:47, , 3F
03/19 22:47, 3F
→
03/19 22:49, , 4F
03/19 22:49, 4F
推
03/19 23:45, , 5F
03/19 23:45, 5F
→
03/19 23:46, , 6F
03/19 23:46, 6F
→
03/19 23:47, , 7F
03/19 23:47, 7F
→
03/19 23:48, , 8F
03/19 23:48, 8F
推
03/20 08:15, , 9F
03/20 08:15, 9F
→
03/20 09:15, , 10F
03/20 09:15, 10F
推
03/20 10:20, , 11F
03/20 10:20, 11F
討論串 (同標題文章)