一、小谈一下算法的复杂度
评判一个算法的好坏，一般是从时间和空间两个维度来衡量的
时间复杂度衡量一个算法的运行快慢，而空间复杂度衡量一个算法所需要的额外空间（但由摩尔定律的存在，空间复杂度不再需要特别被关注）。
二、时间复杂度六点总结
算法的时间复杂度是一个函数（数学上的函数表达式），并且大小由算法中基本操作的执行次数决定（在不同计算机硬件环境下，算法运行速度肯定不一样，运行时间并不好作为参考）。
时间复杂度用大O符号表示，如O(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;
}
printf("%d\n", count);
}
这个算法的精确复杂度为:N^2+2N+10 ,但时间复杂度只需写成O(N^2),
这是因为随着N增大，2N大小相较于N^2显得微不足道
void Func2(int N) {
int count = 0;
for (int i = 0; i < 2 * N; ++i) {
++count;
}
int M = 10;
while (M--) {
++count;
}
printf("%d\n", count);
}
这个算法的精确复杂度为:2*N+10,但时间复杂度只需写成O(N)
void Func3(int N) {
int count = 0;
for (int k = 0; k < 100; ++k) {
++count;
}
printf("%d\n", count);
}
O(1)表示对于常数次数的时间复杂度
【还有三点需要注意的】
1.未知数不一定只能是N
void Func4(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);
}
如上述， 在M与N大小不确定的情况下时间复杂度为：O(M+N) 不然如果M>>N将是O(M),反之。
2.时间复杂度需要看最坏情况下的运行次数
//在一段字符串中找到某个字符
const char* strchr(const char* str, int character) {
while (*str) {
if (*str == character) {
return str;
}
else
++str;
}
}
这个程序最好的情况就是在一开始就找到了需要的字符，当然最坏情况就是找到最后，所以时间复杂度应该是O(N)
3.算时间复杂度不能只去看几层循环，更应该看它的思想
int BinarySearch(int* a,int n, int x) {
assert(a);
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;
else
return mid;
}
return -1;
}
这是一个二分查找算法，时间复杂度为O(log2N)。
二分查找（有序前提）:
一个有N个数的数组，在其中查找一个数，若这个数大于数组中间的值，则取这个数组的大于中间值的数所在的那一半，多次进行这个操作，直到取到这个数，如果找不到这个数则在最后多次取半的数组范围中只有一个数的时候停止。
假设这个操作进行了x次 则有1 * 2 * 2 *…=N 1乘2乘了x次，所以有2^x=N,x=log2N
long long Fac(size_t N) {
if (0==N)
return 1;
return Fac(N - 1) * N;
}
这是一个递归算法， 递归算法的时间复杂度：递归次数*每次递归调用的次数
让我们先看看它的递归次数：从Fac(N)开始
Fac(N)>>Fac(N-1)>>Fac(N-2)>>…>>Fac(1)
而每次递归调用的次数是1，所以这个算法的时间复杂度为O(N)
三、空间复杂度两点总结
空间复杂度也是一个数学表达式（也是用O()表示），算的是变量的个数（开辟内存空间个数），是对一个算法在运行过程中临时额外占用存储空间大小的量度。
注意：函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候申请的额外空间来确定。（如递归算法）
1.函数运行时，空间复杂度主要通过函数在运行时候申请的额外空间来确定
让我们来再次看这个递归算法
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(1)
在函数调用中,每访问一次Fac函数,创建一个栈帧（也可理解为开辟了一块空间）,这里进行了N次，所以空间复杂度为O(N)。
2.考虑一下程序中出现的销毁情况
//这是一个冒泡排序
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;
}
}
看看它的空间复杂度是多少，它很容易被看成是O(N)，但由于i出作用域的销毁，它只对end做了内存开辟，所以空间复杂度应该是O(1)。
让我们再来看看这个 这个可能有点复杂。
long long Fib(size_t N){
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
这也是个递归算法 我们可知在Fib(N)调用后,接下来调用的应该Fib(N-1),并且会一直进行这个函数的运算直至到Fib(1)+Fib(2)， 这个时候将为每次调用创建一块内存空间，所以当Fib(N-1)这一个分支调用完后，开辟了N块内存空间，并且在使用完后将销毁。
再然后才开始Fib(N-2)的计算，这个时候利用的内存空间将是与调用Fib(N-1)分支所开辟的N块内存空间是一样的，所以结果还是N块空间，所以空间复杂度为O(N)。
(右边的是调用次数，不是开辟空间的)
Fac(N) 2^0
↓
Fac(N-1) Fac(N-2) 2^1
↓
Fac(N-2) Fac(N-1) Fac(N-2) Fac(N-3) 2^2
↓
…
↓
Fac(1) Fac(2) 2^(n-1)
如果我们再看看它的时间复杂度
很明显如果没有限定条件，调用次数呈等比数列
但是因为限定条件这个树图的右边会缺少一部分，假设缺少了X个，那么整个就是2^n -1-x,所以时间复杂度为O(2^N).
由此也可以得出：
空间是可以重复利用的，不累计的 。
时间是不可重复利用的，累计的。
总结一下
时间复杂度和空间复杂度在今后的编程道路上是挺常见的，了解到位非常重要。
以上是我对时间复杂度和空间复杂度的所有了解，写这么多也是对自己的一个总结，如果能对你有帮助的话，也没白写 。