目录

递归时间复杂度求解

Sukun 收录于算法与数据结构

2022-03-15 2022-03-15 约 284 字预计阅读 1 分钟次阅读条评论

目录

递归时间复杂度求解

master公式使用

$$ T(N)=a*T(\frac{N}{b})+O(N^d)\\ \log(b,a)>d\qquad时间复杂度O(N^{\log(b,a)})\\ \log(b,a)=d\qquad时间复杂度O(N^d*\log{N})\\ \log(b,a)<d\qquad时间复杂度O(N^d)\\ $$

N为母问题的规模级别，子问题规模都是$\frac{N}{b}$，a是子问题调用次数，$O(N^d)$是除了调用子问题以外的过程的时间复杂度

举个栗子

1
2
3
4
5
6
7
8
9


int process(int arr[], int L, int R)
{
    if (L == R)
        return arr[L];
    int mid = L + (R - L) >> 1; //求中点
    int LMax = process(arr, L, mid);
    int RMax = process(arr, mid + 1, R);
    return RMax > LMax ? LMax : RMax;
}

该递归算法时间复杂度： $$ T(N)=2*T(\frac{N}{2})+O(1) $$