0.前言
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。
本文主要通过大O的渐进表示法对时间复杂度和空间复杂度进行衡量，并通过一些例子说明。
1.大O的渐进表示法
一般来说算法的空间复杂度和时间复杂度都是一个关于n的函数f(n)，例如以下函数func()，我们计算它的时间复杂度。它的执行次数是关于n的函数f(n) = n^2 + 2n + 10 ,但是实际我们计算的时候并不需要精确的执行次数，只需要一个大致的执行次数，这时候就要使用大O的渐进表示法。只取其中具有决定性的那一项。
int func(int n)
{
int count = 0;
//第一段,执行了n*n次
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
++count;
}
}
//第二段，执行了2n次
for (int k = 0; k < 2*n; ++k)
{
++count;
}
//第三段，执行了10次
int x = 10;
while (x--)
{
++count;
}
return count;
}1.1 大O符号
表示一个函数在输入规模趋于无穷大的时候的增长趋势，重点关注的是算法复杂度的上界。记作O(f(n)),f(n)是输入规模为n的某个函数，描述算法的复杂性，然后我们根据推导方法对f(n)做出一些变化。
1.2 推导方法
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
- 如果f(n)是一个常数级别的函数，直接用常数1取代，如f(n) = 10,那么它的复杂度就为O(1)。无论这个常数多大。但是如果常数只是该函数的一项，那么直接忽略该常数，进行下面的步骤。
- 找出f(n)的最高阶的项，例如上面的f(n) = n^2 +2n + 10，它的最高阶的项为n^2
- 如果最高阶项有常数与它相乘，直接忽略这个系数，例如如果我们得到 f(n) = 3n^2,或者 f(n) = 2n,那么直接将它们的系数改为1，分别变为n^2和n，最终得到复杂度O(n^2)和O(n)。
1.3 常见的大O复杂度
时间复杂度本质计算的是算法的量级。
| O(1) | 常数复杂度 |
| O(n) | 线性复杂度 |
| O(n^2) | 平方复杂度(O(n^3),O(n^4)...) |
| O(logn) | 对数复杂度 |
| O(nlogn) | 线性对数复杂度 |
| O(2^n) | 指数复杂度 |
| O(n!) | 阶乘复杂度 |
1.4 最坏运行情况
有些算法的执行次数是不一定的，比如查找算法，我们在查找时可能一次就找到了O(1)，也有可能遍历完数组才找到O(n)。对于这种不确定的复杂度，我们可以分情况讨论：最好情况，最坏情况和平均情况。但是一般我们会只关注它的最坏情况。
eg.计算如下代码的时间复杂度
const char* strchr( const char* str, int character);该函数实现的是在一个字符串中找到一个字符，并且返回第一次出现该字符的指针。此时它的运行次数和时间是一个不确定的值，他的最好情况就是一次找到，最坏情况是N次找到，平均N/2次找到 。因为时间复杂度关注最坏情况，所以这个函数的时间复杂度为O(N).
2.时间复杂度
时间复杂度描述了算法在输入规模增大时，执行所需时间的增长趋势。以下用例子说明。
2.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);
}该函数执行次数为2*N+10，去掉常数10，留下最高阶2*n，去掉系数2，得到n所以时间复杂度为O(n)。
2.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);
}该函数的执行次数为M+N次，然而M和N都是不确定的，所以它的时间复杂度为O(M+N)。
2.3 示例三
void Func3(int N)
{
int count = 0;
for (int k = 0; k < 100000; ++ k)
{
++count;
}
printf("%d\n", count);
}这段代码的执行次数是100000 次，看起来很大，但也是个常数，所以是常数级别的，它的时间复杂度为O(1)。
2.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;
}
}时间复杂度为O(N^2),最坏情况就是每一趟都发生了交换，比较次数为n-1 + n-2 + n-3 + ... + 1 = 2/(n^2 - n). (最好情况就是这个数组本来就是升序排序，比较了n-1次没有发生交换直接结束了，此时时间复杂度为O(N))。
2.5 👉二分查找时间复杂度的计算
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;
}最好情况是一次找到，最坏情况是log(2)N次找到，所以时间复杂度是O(logN)。
区间数据个数：
N
N/2
N/2/2
...
N/2/2/.../2 = 1
假设查找x次，2^x=N。可以得到x = logN（log以2为底N的对数次，但是有些文本不方便，可以直接简写成logN，以2为底的可以省略，其他的要写出来）
2.6 👉阶乘递归函数的时间复杂度
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}大概就是被调用N+1次，每次调用的时间复杂度是O(N),所以这整个递归函数的时间复杂度就是O(N)。
递归算法的时间复杂度是多次调用的次数的累加，eg如果这个函数是这样的👇
long long Fac(size_t N)
{
if(0 == N)
return 1;
for (size_t i = 0; i < N; i++)
{
...
}
return Fac(N-1)*N;
}此时每次调用执行次数都不同，分别是N,N-1，...，1，全部相加，时间复杂度就为O(N^2)。
(时间复杂度是一个大概的计算，一般如果算这些语句中比较不确定或者庞大的部分，比如循环...有些定义语句，返回语句不用加上算得那么精准)
2.7 👉斐波那契递归的时间复杂度
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}斐波那契数列的递归时间复杂度为O(2^N)，因为他又很多重复的执行，导致在时间上的效率低下，如果用循环来计算时间复杂度是O(N)。它在函数体内的执行次数也是O(1)级别的，但是它的调用次数非常多，大致是一个等比数列的相加（当然也不完全是一个等比数列，画图就会发现有一边计算的会少一个，不过这也不影响）
3.时间复杂度
空间复杂度的思想与时间复杂度相似，它计算的是一个算法在运行过程中额外临时占存储空间大小的度量。空间复杂度算的不是程序占用了多少bytes的空间，而是变量的个数。也使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
以下直接通过示例说明
3.1 冒泡排序空间复杂度
冒泡排序在排序过程中并没有新建数组，最多也就几个变量，是常数级别的，因此可以视为没有额外开辟空间，所以它的空间复杂度就是O(1)。
3.2 斐波那契数列空间复杂度
// 计算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;
}因为它在需要返回前n项，函数在函数体内开辟了n+1个空间，这就是额外开辟的空间，所以它的空间复杂度是O(N)。
3.3 阶乘递归空间复杂度
每次递归栈帧需要占常数个空间O(1),需要建立N个栈帧，所以空间复杂度为O(N)。
3.4 斐波那契递归空间复杂度
// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}（递归的最大问题：深度太深，容易栈溢出）
时间是累计的，空间是可以重复利用的 每次递归返回的时候多个函数空间共用同一个栈帧，最多用N块空间。递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)。
虽然这个递归的时间复杂度是O(2^N)，但是它不是每次调用都是需要新的空间建立栈帧的，可以从以下代码理解。
以下代码最后输出两个相同的地址（函数地址是不一样的，函数地址不是栈帧地址，是指令的地址），可能稍微变动就不相同了，以下两个逻辑相似。
-THE END-
