討論串[問題] 資結-時間複雜度
共 7 篇文章
內容預覽:
(a) log(n!) = O(nlogn). Stirling 公式: n!≒n^(n+1/2)*e^(-n). ∴log(n!) ≒ log((n^n+1/2)*e^(-n)) = log(n^n+1/2) + log(e^-n). = (n+1/2) * logn - n. = nlogn +
(還有132個字)
內容預覽:
......= =. lg(n!)=Θ(nlgn). pf: (a) = lg(1*2*3*...*n). = lg1 + lg2 + lg3 + ... +lg n <= nlgn. O(nlgn). = lg1 + lg2 + lg3 + ... +lg n >= lg(n/2)+lg(n/2+
(還有144個字)
內容預覽:
(a) = lg(n * n-1 * n-2 * ... * 1). = lg(n) + lg(n-1) + .... = O (lgn). (c) = O (n^2). b,d,e 各取lg，為b',d',e'. (b') = lgn * lg4 = O (lgn). (d') = lgn + n
(還有173個字)
內容預覽:
Factorial 例如:n!. Constant 例如:10. Log linear 例如:nlogn. Cubic 例如:n^3. Quadratic 例如:n^2. Exponential 例如:2^n. Linear 例如:n. Logarithmic 例如:logn. 所以答案為 b(lo
(還有78個字)