22

数据结构与算法—复杂度分析

 3 years ago
source link: http://www.demanmath.com/index.php/2020/08/30/shujujiegouyusuanfa-fuzadufenxi/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

复杂度分析

复杂度是算法里面最重要的概念，算法的差别就是复杂度分析。

实际的应用场景，一个算法O(n)的，可能比O(1)更快，但是当n非常大的时候，比如服务端上千万的用户，不同的算法产生的效率差别非常大。

一个优秀的算法，就可以节省很多的时间，甚至经济上也有很大的优势。

我们需要一个不依赖于测试用例的方法，来评估每个算法的复杂度，以便我们选择合适的算法来解决问题。

O表示法

分析一段代码的复杂度，就是CPU语句的执行次数，已经所占的内存空间。这2个是程序执行过程中最重要的2个硬件。

我们可以用T(n)来表示，算法的执行效率。

比如：T(n) = n^2+n+4 这个样子，n是数据的规模。

当然也有可能是T(n) = 3这个样子。

我们把这个比较过程优化下，比如，n->∞的时候，低阶的幂次是可以忽律的，应该n^2的速度会远大于n的规模。

所以我们用O(n)这个一个方法来表示算法的扩展规模。或者说

T(n) = O(f(n))来表示。

时间复杂度的特点

只关注最复杂的那一部分

一个程序都有很多行代码，只有循环和递归，才是最复杂的部分。

其他部分，不管有多少行，都是执行一次，这种方式就是 O(1)

所以这些都是可以忽略的。

乘法法则

  • 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    这一部分其实很好理解，比如

    int cal(int n) {
int ret = 0; 
int i = 1;
for (; i < n; ++i) {
 ret = ret + f(i);
} 
} 

int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i;
} 
return sum;
}

    这部分代码看下来，分里外2个部分。

常见的复杂度分析

常见的复杂度分为：O(1),O(n),O(logn),O(nlogn),O(n^2) ...

还有就是O(2^n)和O(n!),这2种效率非常低，所以这种算法一般不会被使用。

  • 一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)
  • 以2的幂次方增长到n的过程，一般就是2^x = n ,x = logn. 常见的算法就是二分法。

空间复杂度分析

空间复杂度是和空间的规模增长才表示的。

空间复杂度一般就是O（1），O（n），O（n^2）


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK