重拾算法与数据结构之时空复杂度

unit_Time:每行代码运行的时间

n^2+2n+1:表示代码执行的行数

n:一行代码的执行次数

按照上面的例子推出大O表达式:

T(n)=O(f(n)):n表示数据规模;f(n)表示代码执行的次数;O表示代码的执行次数与代码的执行时间成正比

所以上面例子可以表示为 O(n^2+2n+1)

大O时间复杂度并不表示代码的执行时间,而是表示代码的执行时间随数据规模的增长趋势,也叫渐近时间复杂度,简称时间复杂度。

当数据规模n很大时,公式中的低阶,常量和系数都不能左右增长趋势,所以可以忽略,只需要记录最大量级,所以如果用大O表示法表示上面的例子O(n^2)

2.时间复杂度分析

1)只关注循环字数最多的一段代码

2)加法原则,这段代码多处循环,总复杂度等于量级最大的代码复杂度

3)乘法原则,嵌套代码的复杂度等于嵌套内外的代码复杂度的乘积。

3.几种常见的时间复杂度分析

重拾算法与数据结构之时空复杂度

对于复杂度量级,可以区分为两类:多项式量级和非多项式量级(O(2^n),O(n!))

对于非多项式量级的问题我们称为NP问题,当数据规模n增加时,非多项式量级的执行时间会急剧上涨,所以非多项式量级的算法是很低效的。

主要介绍下多项式量级的复杂度

1)O(1):并不表示只执行一行代码,而是常量级。并不随n发生变化。

2)O(logn),O(nlogn):

如下代码:

i = 1;

while(i <= n){

i = i*3

}

这段代码的执行次数是log3n 时间复杂度是O(logn)

不管对数的底是多少,我们都可以使用logn表示时间复杂度。这是因为对数间可以相互转换。log3n*log23 = log2n。

3)O(m+n),O(m*n)

代码的复杂度由两个数据规模决定,不能确定m,n谁更大

4.空间复杂度

空间复杂度就是渐近空间复杂度,表示算法的存储空间与数据规模之间增长关系。

int[] a = new int[n];

空间复杂度为O(n);

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zygpgj.html