从严格的数学角度下分析时间复杂度的计算方法

预备知识:

①积分近似:

​ 一般地:

②分治递归式通解:(主定理的原式)

​ 通解为:

​ 其中$\lceil\log_bn\rceil=[\log_bn]-1$,求和部分直接用积分近似计算即可

③衡量算法效率参数

衡量算法效率参数 数学语言 表示
大$O$法 $f(n)\le cg(n)$ $O(g(n))$
大$\Theta$法 $c_1g(n)\le f(n)\le c_2g(n)$ $\Theta(g(n))$
大$\Omega$法 $f(n)\ge cg(n)$ $\Omega(g(n))$
近似法 $\lim_{i\to0}=f(n)/g(n)=1$ $\sim g(n)$

其中大$O$法和大$\Omega$法,常用于时间复杂度的标度。一般来说,时间复杂度用$O$。

for循环

①循环嵌套,变量间无关联

1
2
3
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
...

​ 用求和表示:

​ 计算时间复杂度:

​ 法①:

​ 法②:

​ 故时间复杂度为$O(n^2)$

②嵌套循环,变量间有关联

1
2
3
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
...

​ 用求和表示:

​ 计算时间复杂度

​ 法①:

​ 法②:

​ 在这里可以发现积分的结果一般比离散求和要大,这保证了时间上界,所以积分近似有效且高效。

​ 故时间复杂度为$O(n^2)$

while循环(假设$i$从1开始变化)

①条件变量呈线性变化

​ 直接用for循环的方法即可,但如果增量不为1的话:

1
2
3
4
while(i <= n){
i += 2;
...
}

​ $i$的变化看作是等差数列

​ 那么上述数列有多少项数,那么耗时就为多少:

​ 先写出数列的递归表达式:

​ 计算得出:

​ 令$x(k)=n$,这个时候$k=T(n)$

​ 时间复杂度为$O(n)$

②条件变量呈k次变化

1
2
3
4
while(i <= n){    
i *= 2;
...
}

​ $i$变量每次乘以2,同样可以看成数列,但这个时候$i$的变化为等比数列:

​ 同样的,令数列:

​ 计算得出:

​ 令$x(k)=n$,这个时候$k=T(n)$

​ 时间复杂度为$O(\log n)$

递归式求解

对于递归式,只要求出方程就可以了,一般来说难度不大,下面介绍典型递归式。

线性递归

形如

一般采用数列不动点求出方程

比如

求得

比如

求得数列不动点$x=-n$,构造:

不难得到:

求得:

什么是数列不动点?

对于一阶线性递推数列:

令$xn=x{n-1}=x$,这个$x$就是不动点:

因此:

化简得到:

分治递归

常见的分治递归有如下的表达式:

不难证明出通解为:

其中$\lceil\log_bn\rceil=\log_bn-1$,求和部分直接用积分近似计算即可。

但这还是麻烦点,所以有人通过这个通解总结出了分治递归的主定理方法:

复杂的分治递归需要用到换元法等知识,比如求解:

这时候我们需要对这个式子进行变式:

令$n=2^m$,于是:

令$P(m)=T(2^m)$,那么

这个时候就好解决了,可以求出来这个递归式的时间复杂度为$O(m)$(属于主定理的第一种情况,$n^{log_ba}=n^1$,并且$f(n)=1=n^0=O(n^{1-\epsilon}),当$$0<\epsilon \le1$成立)

换元回来就得到:$O(\log n)$

总结

​ 时间复杂度不难分析,只需要观察代码,然后分析是啥变量在变化,条件是啥。然后用数列表示出这个变量,那么这个数列的项数就是时间函数,求出时间函数一切都好办辣!

​ 对于增量不为1的情况,还是构造数列$x(k)$,解出$x(T(n))=n$这个方程就可以了!

从严格的数学角度下分析时间复杂度的计算方法

http://blog.inverseda.top/2022/03/01/算法笔记/时间复杂度计算方法/

Author

InverseDa

Posted on

2022-03-01

Updated on

2023-03-30

Licensed under

Comments

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×