从例子来学习算法的时间复杂度

in 电脑技巧 代码 with 0 comment

前言

时间复杂度能用来衡量一个算法的快慢
我们常用 大O表示法 来表示

阅读本篇文章,你需要有

  1. 程序语言基本知识
  2. 常见程序语言的循环,判断知识

例子

我们将通过不同的例子来向你展示不同的复杂度代表怎样的程序

1.时间复杂度为O(1)

其实就是执行一次的程序
比如:

java: int i=1;
php: $a=1;
js: var aa=1;

这些都是复杂度为O(1)的程序

2.时间复杂度为O(n)

这可能是你很好奇的一个,也是很常见的一个

for(int i = 0; i < n; i++){
   int a = 0; //执行N次
}
a = 1;//执行1次

这里按理来说应该是O(n+1),但实际上我们需要将1忽略
我们需要记住几条简化规则

1. 去掉加法常数

例: n+1+1=n
n+10+1=n

2. 只保留最高项

例: n²+n+1=n²

3. 最高项系数为1

例: 2n²+n+2=n²
4n²+n=n²

2.时间复杂度为O(n²)

看完上面的你应该已经想到复杂度为n²的程序了

   for(int i = 0; i < n; i++) {         
       for(int j = 0; j < n; j++) {    
           int a=1;
       }
   }

拓展

所有时间复杂度的排序如下:
O(1)<O(logn)<O(n)<O(n²)<O(n³)<O(2^n)

Responses