算法的时间复杂度

04 August 2017

最近在学习算法，所以顺便了解了下算法的时间复杂度。

1. O(1)

temp = i;
i = j;
j = temp;

该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。

2. O(n^2)

for(i = 1; i < n; i++){
  y = y + 1;
  for(j = 0;j <=(2*n);j ++){
	x++;
  }
}

时间复杂度 $T(n) = O(n^2)$

3. O(n)

a = 0;
b = 1;
for(i = 1;i <= n;i ++){
  s = a + b;
  b = a;
  a = s;
}

时间复杂度 O(n)

4.O(log2^n)

i = 1;
while(i <= n ){
  i = i*2;
}

时间复杂度 $O(log2^n)$

5. O(n^3)

for(i = 0;i < n;i ++){
  for(j = 0;j < i;j ++){
    for(k = 0;k < j;k++){
      x = x+2;
    }
  }
}

时间复杂度 $O(n^3)$

常用的算法时间复杂度和空间复杂度

— Kong Jing