复杂度分析

/ 计算机基础 / 175浏览

复杂度分析

数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行的更快,如何让代码更省存储空间。所以,执行效率是算法一个非常重要的考量指标。那么如何来考量呢?

答案就是:时间、空间复杂度分析。掌握了时间、空间复杂度分析,就能更好地应用数据结构和算法。

大O表示法

算法的执行效率,粗略地讲,就是算法代码执行的时间。就是在不运行代码的情况下,用 “肉眼” 来观察到代码的大约执行时间。

比如下面代码:

int sum = 0;
for(int i=0;i<n;i++){
    sum += i;
}
System.out.println(sum);

第一行执行1次,第二行开始到第四行是一个循环,循环了n次,第五行执行了一次,假设每行代码执行的时间都一样,为unit_time,那么整段代码执行时间为:(n+2)*unit_time 次,所有代码的执行时间T(n) 与每行代码的执行次数成正比。

按这个思路分析,尽管我们不知道unit_time的具体值,但通过这段代码执行时间的推导过程,可以得到一个非常重要的桂林,就是所有代码的执行时间T(n)与每行代码的执行次数n成正比。我们可以把这个规律总结一个公式,就是:

alt

这就是大O表示法,即 “大约” 表示法。

时间复杂度

因为不是非常精确的,但是所表达的是代码执行时间随数据规模增长的变化趋势,所以也叫渐进时间复杂度。

常见复杂度量级主要分为2大类,**多项式量级 **和 非多项式量级。如图:

alt

O(1) 只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码。

O(logn)、O(nlogn) 对数阶时间复杂度,归并排序、快速排序的时间复杂度都是 O(nlogn)

按复杂度量级排序,从低阶到高阶有,O(1)、O(logn)、O(n)、O(nlogn) ....:

alt

空间复杂度

算法占用空间大小称为空间复杂度。对于好的算法评判标准就是高效率、低存储。

比如排序算法中的,计数排序就用了额外的空间,而归并排序、插入排序等算法就没有用额外的空间存储。