1.算法的复杂度
算法在编写为可执行程序后，运行需要耗费时间资源和空间资源。所以衡量一个算法的好坏，一般都是从时间和空间两个维度来衡量的。
而时间复杂度主要是衡量算法的运行快慢的，空间复杂度则是衡量算法运行所需的空间。
所以本篇文章将仔细讲解时间复杂度的概念和计算。
2.时间复杂度
1.时间复杂度的概念
时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了算法的运行时间，一个算法所执行耗费的时间。但是每个机器都是不一样的，并且所有算法都放到机器上跑来计算时间是很麻烦的。所以才有了时间复杂度的分析方式，一个算法所花费的时间与代码中语句的执行次数成正比，算法中的基本操作的执行次数，为算法的时间复杂度。
2.大O渐进表示法
我们先计算一下Fun函数的count执行次数
void Func(int N)
{int count = 0;for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){count++;}}for(int n = 0; n < 2*N; n++){count++;}
}Func的执行基本操作次数：
N=10 Func(N) = 120 Func(N) = N^2+2*N
N=100 Func(N) = 10200
N=1000 Func(N) = 1002000
实际我们计算时间复杂度是不需要计算精确的执行次数的，只需要大概的执行次数，所以我们使用在书上和刷题网站上经常看到的大O渐进表示法。
大O符号：Big O notation 用于描述函数渐进行为的数学符号。
推导大O阶的方法：
1.当运行时间中都是加法常数时，使用常数1。O(1)
例：
void Func()
{int count = 0;for(int i = 0; i < 100; i++){++count;}printf("%d", count);
}Func() = 100 ------> O(1)
2.在修改后的运行次数函数中，之保留最高项
3.如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶
void Func(int N)
{int count = 0;for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){count++;}}for(int n = 0; n < 2*N; n++){count++;}
}所以使用大O的渐进表示法后，Func的时间复杂度为：
Func(N) = N^2+2*N ------> O(N^2)
我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁表面了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数
例：
void Bubblesort(int* a, int sz)
{for(int i = 0; i < sz-1; i++){int exchange = 0;for(int j = 0; j < sz-1-i; j++){if(a[j] > a[j+1]){int tmp = a[j];a[j] = a[j+1];a[j+1] = tmp;exchange = 1;}}if(exchange == 0)break;}
}冒泡排序的时间复杂度：
最好情况： O(N) 数组本身是有序的
平均情况：可能只需要最坏情况的一半时间
最坏情况： O(N^2) 数组每个元素都需要排序
所以我们在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N^2)
3.常见时间复杂度计算举例
例1：
void Func1(int N)
{int count = 0;for (int k = 0; k < 2 * N ; ++ k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}Func1(N) = 2N+10 -----> 根据大O渐进表示法，去除常数----->O(N)
例2：
void Func2(int N, int M)
{int count = 0;for (int k = 0; k < M; ++ k){++count;}for (int k = 0; k < N ; ++ k){++count;}printf("%d\n", count);
}Func2 = M+N -----> 两个变量都不是常数 ----->O(N+M)
如果知道M或N比对方过大，不只是比对方大，而是大出很多，则可以为O(N)/O(M)
例3：
const char * strchr ( const char * str, int character );strchr这个函数是查找字符串中是否有 character这个转换为了数字的字符；
而最差的情况是需要将整个字符串遍历找到character。
所以这个函数的时间复杂度为O(N)
例4：
int BinarySearch(int* a, int n, int x)
{int begin = 0;int end = n-1;while (begin <= end){int mid = begin + ((end-begin)>>1);if (a[mid] < x)begin = mid+1;else if (a[mid] > x)end = mid-1;elsereturn mid;}return -1;
}这是二分查找---->每次折半查找，所以效率是最高的 O(logN) logN底数为2
基本操作执行最好1次，最坏O(logN)次，时间复杂度为 O(logN) ps：logN在算法分析中表示是底
数为2，对数为N。有些地方会写成lgN。（建议通过折纸查找的方式讲解logN是怎么计算出来的）
例5：
long long Fib(size_t N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}这是一个斐波那契函数，函数操作递归了2^N次，就如同二叉树一直递归到Fib(n-1) Fib(n-2) Fib(n-2) Fib(n-3).... Fib(3) Fib(2)，所以时间复杂度为O(2^N),这也是最耗费时间的复杂度之一。
