討論串[理工] [資結]-時間複雜度
共 38 篇文章
內容預覽:
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) =
(還有47個字)
內容預覽:
(a)2n = O(n). (b)nlog 8+log n = O(n)+O(lgn) = O(n). (c)16^ n-10 = O(16^n). (d)64 = O(1). (e) (log n)^2 = O(lgn*lgn). (f)n^3. (g) 4^log n = n^lg4 = n^2
(還有58個字)
內容預覽:
Order the following functions by their growth rates starting with the slowest. (a)2n (b)nlog 8+log n (c)16^ n-10 (d)64 (e) (log n)^2. 2 2. (f)n^3 (g)
(還有30個字)
內容預覽:
T(n) = 2^n*T(0)+n+2(n-1)+2^2(n-2)+...+2^(n-1). let S = n+2(n-1)+2^2(n-2)+...+2^(n-1). 2S = 2n+2^2(n-1)+2^3(n-2)+...+2^(n-1)*2+2^n. 2S-S = -n + [2+2^2+
(還有58個字)