T(n - 1) = k(n - 1) + T(n - 2) + ... + T(2) + T(1) ---- (2)
(1) - (2)
<=> T(n) - T(n - 1) = kn - k(n - 1) + T(n - 1)
<=> T(n) = 2T(n - 1) + k
<=> O(2^n)
Permutations
T(n) = nT(n-1) + C
<=> O(n!)
2016年7月19日星期二
Time Complexity of Permutations and Subsets
Subsets
T(n) = T(n - 1) + T(n-2) +...+ T(2) + T(1) + C (Q: How to calculate this?) (Wrong!)
T(n) = kn + T(n - 1) + T(n - 2) + ... + T(2) + T(1) ---- (1)
T(n - 1) = k(n - 1) + T(n - 2) + ... + T(2) + T(1) ---- (2)
(1) - (2)
<=> T(n) - T(n - 1) = kn - k(n - 1) + T(n - 1)
<=> T(n) = 2T(n - 1) + k
<=> O(2^n)
Permutations
T(n) = nT(n-1) + C
<=> O(n!)
T(n - 1) = k(n - 1) + T(n - 2) + ... + T(2) + T(1) ---- (2)
(1) - (2)
<=> T(n) - T(n - 1) = kn - k(n - 1) + T(n - 1)
<=> T(n) = 2T(n - 1) + k
<=> O(2^n)
Permutations
T(n) = nT(n-1) + C
<=> O(n!)
订阅：
博文评论 (Atom)
没有评论:
发表评论