分支算法的时间复杂度
记录一下
表示将原问题分解成 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 时
具体过程展开图如下:
推到过程如下: