时间复杂度

算法的时间复杂度是一个函数。但不是计算时间，是操作的大概执行次数。

大O的渐近表示法

O(1)表示常数次。（常数用1来代替。）

1
2
3
4
5
6
7
8

for(int i=0;i<2*n;i++){
	for(int j=0;j<n;j++){
		ans++;
	}
}
for(int i=0;i<10;i++){
	ans++;
}

以上f(n)=2*n*n+10;
O(n^2）

时间复杂度看最坏情况。

冒泡排序

由冒泡排序算法的定义可得时间复杂度是等差数列求和：

(n-1)+(n-2)+(n-3)…+2+1
即为(n*(n+1))/2，所以O(n^2)

当然，O(n^2)是最坏情况。
最好情况是当数列是有序状态时，时间复杂度是O(n);

二分查找

二分查找的情况只有两种：

1. 找到了
2. 范围缩小一半

所以最坏情况是范围缩小到为1时。

即：N/2/2/2/2…=1;
N=2^x;
x=logN;

所以**时间复杂度为O(logn)**。
按照函数图像可知，数字越大，上升越慢，但是二分的前提是有序数列。

斐波那契

真的非常慢。

2^0+2^1+2^2+2^3…..2^(n-1)=2^n-1;
所以时间复杂度为O(2^n)