您现在的位置:首页 > >

关于408时间复杂度*题计算的理解

发布时间:



关于时间复杂度的计算理解
前言一、循环的 判定条件 没有主体变量的参与1.1 非递归程序1.1.1 最基础类型1.1.2 迷惑类型1.1.2.1 猜测+验证法1.1.2.2 级数求和

1.2 递归程序1.2.1 代入法1.2.2 主定理法1.2.3 递归树法

二、循环的 判定条件 有主体变量的参与



前言

如果代码的执行最多总次数可以被表示为一个多项式。
那么时间复杂度就是

???保留最高次方、且去掉常数。
之后的结果。 所以,求一段代码的时间复杂度,就是 得到关于次数 t 的多项式,再去掉常数和保留最高次方即可。


然而,求出 t 并不是那么容易的。要懂得如何从代码中提取出 t 的多项式。

主要分为以下两种题型:



一、循环的 判定条件 没有主体变量的参与


此类问题的又可分为两种类型



1.1 非递归程序
1.1.1 最基础类型

for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
for(int k = 0; k < 2; ++k)
A[i][j] = 100;

for(int i = 0; i < n; ++i)
cout << "999" << endl;

第一段代码是三层循环嵌套,第二层代码是一层循环。
可以轻易的看出,
?第一段代码最内层的语句最多执行




2



n


2




2n^2


2n2 次.
?第二段代码最内层最多执行 n 次
所以此段代码的?最多情况下?的总执行次数为




2



n


2



+


n



2n^2+n


2n2+n 次,
若记执行次数为, 则





t


<


=


2



n


2



+


n



t <= 2n^2+n


t<=2n2+n
根据 “留高次,去常数” 的原则,




0


<


t


<


=



n


2




0 < t <= n^2


0用 “大 O 表示法” 记为





O


(


2



n


2



+


n


)



O(2n^2 + n)


O(2n2+n)
但是当




n









n oinfty


n→∞ 时, 后面的低次项 n 与常系数 2 就显得微不足道了。所以为了更简洁的描述与比较快慢,可记为





O


(



n


2



)



O(n^2)


O(n2)


1.1.2 迷惑类型

还是刚刚的那段代码,只不过做了些许的改动。就足以让很多同学迷惑



for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j)
for(int k = 0; k < 2; ++k)
if(A[i][j] > 999)
A[i][j] = 100;

for(int i = 0; i < n; ++i)
cout << "999" << endl;

可以看出,此程序执行次数最多可能的语句还是 第一层循环的最内层语句


A[i][j] = 100;

这样的语句我们称为 主体语句
所以根据?留最高, 去常数。原则,我们只关心主体语句的执行过程,而不用去管第二个循环。此时代码简化为:


for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j)
for(int k = 0; k < 2; ++k)
if(A[i][j] > 999)
A[i][j] = 100;

又,第三个循环的作用不过是给执行次数 t 的多项式添上系数 2 而已,所以也可以去掉。


for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j)
if(A[i][j] > 999)
A[i][j] = 100;

为什么不去掉 判断语句 呢??因为我们期望得到主体语句的最高执行次数,所以期待每次 判断语句 都会执行。所以在判断复杂度的时候,所以此时可以忽略判断语句。
即:


for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j)
A[i][j] = 100;

此时有两种方法解决这个问题:


1.1.2.1 猜测+验证法

第一个循环从 0到n-1 共会执行 n 次
而对于第二个循环对的执行次数取决于第一个循环。



但在最多情况下,
也就是 i = n 时,
第二个循环也会执行到 j = n.
此时两个循从 1 到 n 都执行了 n 次. 所以复杂度依然为




n


?


n


=


O


(



n


2



)



n cdot n = O(n^2)


n?n=O(n2)


1.1.2.2 级数求和


众所周知,当 i = n 时,j所在的循环会执行n次,其中每一次都会使主体语句执行 1, 2 … n 次。
次数如上表所示,所以总执行次数为

?留最高, 去常数。后,为




O


(



n


2



)



O(n^2)


O(n2)


1.2 递归程序
1.2.1 代入法






T


(


n


)


=



{













1







,








n


=


1


,










2


T


(


n


/


2


)


+


n









,








n


>


1.









T(n)=left{ egin{aligned} & 1 & , & n=1, \ 2T(n/2)+n & , & n>1. end{aligned} ight.


T(n)={2T(n/2)+n?1,?,n>1.?n=1,
此类问题分四步走:


    写 T(n) 的迭代式(一直文本替换迭代下去)。对每次迭代标号,从1到m。利用 m 与递归截至条件的关系式 解出 m, 代回迭代式。留最高,去常数。

1.2.2 主定理法
1.2.3 递归树法
二、循环的 判定条件 有主体变量的参与

例题如下:



?我们可以观察到:主体语句执行多少次 取决于 绿色框的值 是否符合循环的判定条件


此时,我们是无法得知主体语句的循环次数 t 到底是多少的。
这是由于主体语句的循环与否,是取决于循环条件的。
?如果满足判定条件,则主体语句循环,循环次数增加。
此类题的解题步骤一般分为 4 步:


    列出 主体语句的执行次数绿色框值 的表格
    以第一个为例:

    建立 F(t) 方程
    ??其中自变量 t 为 主体语句的执行次数,因变量为 绿色框值

    将 F(t) 代回循环中的判定条件式,解出 t 变量。
    ??以第一个为例:







n


?


(


t


+


1



)


2




?


n


?



t


2



+


t



?



n



?


t


+



t




n geqslant (t+1)^2 \ Rightarrow n geqslant t^2 + t \ Rightarrow sqrt{n} geqslant t + sqrt{t}


n?(t+1)2?n?t2+t?n
??t+t
?
4. 留高次,去常数





t






n






















O


(



n



)



t leq sqrt{n} \ 时间复杂度为 O(sqrt{n})


t≤n
?时间复杂度为O(n
?)


热文推荐
猜你喜欢
友情链接: 团党工作范文 工作范文 表格模版 社科文档网 营销文档资料 工程文档大全