实例6:计算BinarySearch的时间复杂度
// 计算BinarySearch的时间复杂度？ 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; else return mid; } return -1; }
图解:
假设找了x次，那么除了x个2
2^x =N --> x = log2N
所以说可以从最后一次查找一直乘2，乘到原数组的长度
实例6基本操作执行最好1次，最坏O(log2N)次，时间复杂度为 O(log2N) ps：logN在算法分析中表示是底数为2，对数为N。有些地方会写成lgN。
实例7: 计算阶乘递归Fac的时间复杂度
计算下面两段代码的时间复杂度
//实例7: // 计算阶乘递归Fac的时间复杂度？ long long Fac(size_t N) { if (0 == N) return 1; return Fac(N - 1) * N; } long long Fac(size_t N) { if (0 == N) return 1; for (size_t i = 0; i < N; i++) { } return Fac(N - 1) * N; }
图解:
左边的每一次函数调用里面的for循环语句(如果有其它循环语句也会算上)的执行次数,左边的1表示它是常数次，而不是1次(就说如果函数里面没什么循环语句，有几个if语句，那时间复杂度也是O(1))。
右边的简单来说就说有N+1个函数调用,而每一个函数调用里面的循环语句都执行了N+1次,所以应该把每次的递归调用的函数里面的循环语句都加起来。
补充的点:
时间是加起来的,不是乘起来的，就比如说上图的return Fac(N-1)*N:表示的是上一次的结果乘N,但是执行次数也是一次,因为这个地方的*对于计算机来说仅仅是一个指令。时间复杂度算的是这个程序在走的过程中这个指令的执行次数。
实例8:计算斐波那契递归Fib的时间复杂度
// 计算斐波那契递归Fib的时间复杂度？ long long Fib(size_t N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); }
图解:
执行次数之和符合等比数列：使用错位相减法
这题可以这样理解:
关于那个三角形，白色的区域在N越大的情况下，就会远远大于黑色区域，而时间复杂度是用来计算大致计算某个数学函数是的量级的，给它分一个级别，所以可以看作是满项的状态下计算，然后执行次数之和构成等比数列,用大O渐进表示法去算时间复杂度为O(2^N)。
3.算法的空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中 临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以空间复杂度算的是 变量的个数 。
空间复杂度计算规则基本跟实践复杂度类似，也使用 大O渐进表示法 。
注意： 函数运行时所需要的栈空间 ( 存储参数、局部变量、一些寄存器信息等 ) 在编译期间已经确定好了，因 此 空间复杂度 主要通过函数在运行时候显式申请的 额外空间 来确定。
实例1：计算BubbleSort的空间复杂度
// 计算BubbleSort的空间复杂度？ 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; } }
因为这里只创建了一个end，exchange，i三个变量,只计算变量个数,不管变量类型也不算空间具体的字节数，而且都是在循环里创建的，所以空间复杂度为O(1)。
而关于形参int *a,和int n，它们不会被算在空间复杂度中。
实例2：计算Fibonacci的空间复杂度
// 计算Fibonacci的空间复杂度？ // 返回斐波那契数列的前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; }
空间复杂度，它计算的是你在这个函数内部开辟了多少额外空间，如果是常数个的话，就是O1，如果开辟的大小不确定，一般就是O(N)。
所以说空间复杂度为O(N)。
实例3：计算阶乘递归Fac的空间复杂度
// 计算阶乘递归Fac的空间复杂度？ long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }
图解:
递归调用了N层每次调用建立一个栈帧，每个栈帧使用了常数个空间O(1)
由于这里调用了N个函数,同时没有返回,所以合起来就是O(N)
实例4:计算斐波那契递归Fib的空间复杂度(两个递归)
// 计算斐波那契递归Fib的空间复杂度？ long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
前言:
空间的销毁不是整没了那块空间，是归还使用权，归还给操作系统。
因为内存空间是属于操作系统进程的，比如说让你malloc一块空间，就获得这块空间的使用权，free一下就把空间使用权还给操作系统了
时间是一去不复返时间是累积计算的,空间是可以重复利用不累积计算
简单的说，右边的函数和左边的函数共用一个栈帧。
代码运行:栈是向下生长的,调用Func1和Func2相当于共用一块空间，因为Func1销毁之后，到Func2创建，位置还是那个位置，地址也是那个地址。
因为主函数的a和Func1的a在不同栈帧里面，所以可以同名。
实例4递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)
调用时，建立栈帧;
返回时，销毁。(归还给操作系统)
4.常见复杂度对比
一般算法常见的复杂度如下：
图解：
本章完，如有不足之处，欢迎大佬指正。
