分支算法的时间复杂度
记录一下
表示将原问题分解成 a 个 规模大小为 N/b 的子问题，合并这 a 个子问题的代价是 Θ(NK)
T(N)=aT(N/b)+Θ(NK)
T(N)的解有以下三种情况：
-
T(N)=O(N(logab)) 当 a > bk 时
-
T(N)=O(Nk log^N) 当 a = bk 时
-
T(N)=O(Nk) 当 a < bk 时
具体过程展开图如下：
推到过程如下：
记录一下
表示将原问题分解成 a 个 规模大小为 N/b 的子问题，合并这 a 个子问题的代价是 Θ(NK)
T(N)=aT(N/b)+Θ(NK)
T(N)的解有以下三种情况：
T(N)=O(N(logab)) 当 a > bk 时
T(N)=O(Nk log^N) 当 a = bk 时
T(N)=O(Nk) 当 a < bk 时
具体过程展开图如下：
推到过程如下：