一.算法复杂度
算法在编写成可执行程序以后，运行时需要耗费时间资源和（内存）资源。因此衡量一个算法的好坏，一般是从时间、空间两个维度来衡量的，即时间复杂度和空间复杂度。
现如今，计算机内存越来越大，所以空间复杂度已经不是最主要的考量标准了；现在会比较注重时间复杂度的考量。
二.时间复杂度
时间复杂度定义：算法的时间复杂度是一个函数（此函数非彼函数），它定量描述了该算法的运行时间。一个算法所花费的时间与其中语句的执行次数形成正比例，算法中的基本操作的执行次数，为算法的时间复杂度
即找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度
1.基础时间复杂度
void Func1(int N)
{int count = 0;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){++count;}}for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}
}基本语句与问题规模N之间的数学表达式可以抽象地看成，循环语句共执行了多少次，在最开头的部分，循环语句出现嵌套，被嵌套的循环语句每循环N次，外面的语句循环1次，因此共循环N^2次.接下来的循环语句共循环2*N次,以及共循环10次.所以函数表达式应该为 N^2 + 2*N + 10
请判断下面三种情况下的时间复杂度分别应该是多少?
1. F(N) = N^2 + 2*N +10
2. F(N) = N + 100
3. F(N) = N^3 + N
在时间复杂度计算时，我们一般只会使用到渐近表示法，即O(N)。即只判断算法属于哪个量级。
就拿情况1来举例
N = 10 F(N) = 130 N^2 = 100
N = 100 F(N) = 10210 N^2 = 10000
N = 1000 F(N) = 1002010 N^2 = 1000000
通过上述例子，我们不难发现 N^2 对整个函数表达式影响是最大的，因此当我们在使用渐近表示法时，只保留对整个函数式影响最大的那项(或许会有读者疑惑:那N = 10时,其他项对函数表达式影响也非常大,可为什么就只考虑N很大的情况呢?这是因为现如今的CPU都太过强大,一秒可以执行上亿条语句;因此执行的代码量很小的情况下,可以近似为是相等的时间复杂度,因此不去考虑N很小的情况)，即只保留N^2，因此情况1最后结果为O(N^2)。同理可得，情况2结果为O(N)，情况3结果为O(N^3).
请判断下述情况的时间复杂度
F(N) = 2*N + 10
上述情况下,无论N的系数大小为多少,我们都会把N的系数去除.
我们可以假设一种情况,即有个富翁a身价1000亿,有个富翁b身价2000亿,他们两个虽然在身价上相差两倍,但是豪宅和跑车对于他们来说同样便宜.因此我们完全可以把N前的系数忽略不计
因此上述情况,结果为O(N)
请判断下述两种情况的时间复杂度
1.O(M+N),M远大于N
2.O(M+N),N远大于M
上述情况下,如果M大那就保留M;如果N大就保留N.
因此,最后的结果为情况1是O(M),情况2是O(N)
请判断下述情况的时间复杂度
F(N) = 100
最后结果为O(1),此处的O(1)代表的不是1次,而是常数次
const char * strchr ( const char * str, int character )
{while(*str){if(str == character){return str;}else++str;}上述代码中，最好的情况为O(1)，最坏的情况为O(n)。根据大O渐进表示法，保留最差的情况，因此结果为O(n)。
void func(int n)
{int x=0;for(int i=1;i<n;i*=2){x++;}
}假设循环了x次，那么1×2×2×2×2×……×2=n。因此 2^x = n，x = 。在计算机中，由于
比较难表示出来，因此一般性会把
表示成
。所以上述代码的时间复杂度为O(
)。
2.clock函数介绍
int main()
{int begin1 = clock(); //语句1int n = 100000000;int x = 10;for (int i = 0; i < n; ++i){++x;}int end1 = clock(); //语句2printf("%d ms\n", end1-begin1);return 0;
}在上文中,笔者已经提到：问题规模的大小会影响时间复杂度。而C语言自带的clock函数就是为了搞清楚代码语句之间的用时（例如上述代码，clock函数用来计算从语句1到语句2所花费的时间）。打印出来的结果如下所示
3.时间复杂度总结
大O符号：是用于描述函数渐近行为的数学符号。（本质：计算时间复杂度属于哪个量级）
推导大O阶方法：
- 用常数1取代运行时间中所有的加法常数
- 在修改后的运行次数函数中，只保留最高阶数
- 如果最高阶数存在且不是1，则去除这个项目相乘的常数。得到的结果即为大O阶。
4.常见算法的时间复杂度
- 冒泡排序
void BubbleSort(int* a, int n) { assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}前后两者 一 一依次 比较，第一次遍历比较能确定1个数字的位置，第二次遍历（此时有一个数字可以不参加比较）比较能确定2个数字的位置……；因此时间复杂度为 N-1（第一次比较）+N-2（第二次比较）+N-3+……+2+1，结果即为 (N(N-1))/2。根据大O比较法，结果为O(N^2)。
- 二分查找
int BinarySearch(int* a, int n, int x) {assert(a);int begin = 0;int end = n-1;// [begin, end]：begin和end是左闭右闭区间，因此有=号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; }假设有n个数，最好的情况是直接找到
其他情况下，每次二分查找都能排除摆除一半的非所求数字
就是 n n/2 n/4 …… 4 2 1 这样的一个规律
因此，在最坏情况下（查找区间只剩一个数，或者没找到），n/2/2/……/2 = 1 。查找了x次，就除了x次2。因此2^x = n，最后时间复杂度为 log N 。
二分查找的缺点：a.需要排序 b.不便于插入删除
- 递归阶乘实现
long long Fac(size_t N) {if(0 == N)return 1;return Fac(N-1)*N; }递归相当于多个函数调用的累加和
阶乘函数是Fac(N) Fac(N-1) Fac(N-2) …… Fac(2) Fac(1) Fac(0)
因此总共调用了 N+1 次Fac函数，最后时间复杂度应为O(N)
- 递归阶乘实现 + 函数中加上循环
long long Fac(size_t N) {if(0 == N)return 1;for(int i=0;i < N;i++)
{//……
}return Fac(N-1)*N; }如下图所示，第一函数调用中，共循环了N次；第二次循环函数调用中，循环了N-1次。构成了等差数列，最后结果为 (N(N+1))/2 。因此时间复杂度为O(N^2) 。
- 斐波那契数列求和递归实现
long long Fib(size_t N) {if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}在探讨该问题前，需要先明白：递归时间复杂度是所有递归调用次数求和。
如下图所示，第一层中，函数调用了 Fib(N-1) 和 Fib(N-2)；第二层中，Fib(N-1) 和 Fib(N-2) 分别调用了2次函数，总共调用了4次；由此可得，最后一次调用，总共调用了2^(N-2)。
每层调用次数之间构成了公比为2的等比数列，总层数可以通过最左边的一条结点链条（即 Fib(N-1) -> Fib(N-2) -> …… -> Fib(3) -> Fib(2)）得出。即有 2^(N-1) 层，那么最后一层调用了 2^(N-2) 次。
构成了等比数列，最后求和结果为 2^(N-1)-1 。因此时间复杂度为O(2^N)，非常惊人的高，所以一般不推荐使用递归来实现斐波那契数列求和。（总不能放进去一个100，告诉用户数字太大了换个小点的吧doge）
注意：这边的最后一层的2^(n-2)次运算是估算，实际上并没有进行那么多次。这是因为最左边的那一连串结点每次是 -1，最右边那一连串结点每次是 -2 。因此可以发现，最后的调用次数图右小角那块会是缺失的，就像下图一样。（灰色代表空）
三.空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中 临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用 大 O 渐进表示法 。注意： 函数运行时所需要的栈空间 ( 存储参数、局部变量、一些寄存器信息等 ) 在编译期间已经确定好了，因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。总结：空间复杂度为解决某个问题时，额外开辟的空间。（常见的空间复杂度只有 O(1) 、O(N) 和 O(N^2) ）
常见算法的空间复杂度：
- 冒泡排序
没有新开辟任何的数组，因此为O(1)
- 递归阶乘实现
每次函数调用都需要建立栈帧，总共会开辟n个栈帧，因此空间复杂度为O(N)
- 斐波那契数列求和递归实现
总共开辟了N个函数栈帧，因此空间复杂度为O(N)
- 斐波那契数列求和数组实现
long long* Fibonacci(size_t n) {if(n==0)return NULL;long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; ++i){fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}return fibArray; }开辟了一个新数组，因此空间复杂度为O(N)
