前言
算法就是定义良好的计算过程，它取一个活一组的值输入，并产生出一个或一组值作为输出。简单来说，算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
一、算法效率
如何去衡量一个算法的好坏？
算法在编写成可执行程序后，运行时消耗时间和空间资源。因此，一般从时间和空间两个维度来衡量，即时间复杂度和空间复杂度。
时间复杂度和空间复杂度
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行时所需要的额外空间。
在计算机发展的早期，计算机的存储容量很小。所以对复杂度很是在乎。但是计算机行业的迅速发展，计算机存储容量已经达到很高的程度，所以我们并不用特别关注算法的空间复杂度
二、时间复杂度
时间复杂度是指算法在执行过程中，所需要的时间资源和问题规模之间的关系，主要衡量算法的运行效率，用来估算算法在不同规模下的运行时间
时间复杂度用大O的渐进表示法来表示
2.1时间复杂度的计算
算法的时间复杂度是一个函数式T(N)，它定量描述了该算法的运行时间。
实际上，我们计算时间复杂度时，计算主要涉及到以下几个方面
基本操作次数： 时间复杂度的计算通常关注算法中执行的基本操作次数，例如赋值操作、比较操作、算术运算等。通常将这些操作的数量与输入规模相关联。
循环结构： 算法包含循环结构，需要考虑循环的迭代次数以及每次迭代中的基本操作数量。
递归调用： 对于递归算法，需要考虑递归的深度以及每次递归调用的时间复杂度。通常使用递归方程（递归关系式）来表示递归算法的时间复杂度。
分支结构： 如果算法包含分支结构，需要考虑每个分支的执行次数以及分支中的基本操作数量。
输入规模： 时间复杂度的计算通常与输入规模有关。输入规模表示算法操作的数据量或问题的大小，通常用符号n表示。
说白了，算法复杂度其实就是计算基本操作的执行次数
看一个案例，来计算时间复杂度
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; } }
这里Func函数基础语句执行次数 T(N)=N^2+2N+10
用大O的渐进表示法表示就成了 O(N^2)
大O的渐进表示法
1 . 时间复杂度的函数式T(N)中，只保留最高阶项，去掉那些低阶项
2 . 如果最高项存在且不是1，则去掉这个项的常数系数
3 . T（N）中如果没有N的相关项，只要常数项，用常数1来取代所有加法常数
2.2、时间复杂度计算实例
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); }
Func1函数基本操作次数
T（N）= 2N+10
大O渐进表示法 Func1的时间复杂度为：O(N)
2.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); }
Func1函数基本操作次数
T（N）= M+N
因为这里无法确定M和N的大小，所以有大O渐进表示法 就为：O(M+N)
2.2.3、示例三
void Func3(int N) { int count = 0; for (int k = 0; k < 100; ++k) { ++count; } printf("%d\n", count); }
Func3函数的基本操作次数
T（N）=100
用大O渐进表示法 表示 O(1)
2.2.4、示例四
const char* strchr(const char * str, int character) { const char* p_begin = s; while (*p_begin != character) { if (*p_begin == '\0') return NULL; p_begin++; } return p_begin; }
这里计算strchr函数的基本操作次数
如果查找的字符在字符串的第一个位置（靠前的位置）则T（N）= 1
如果查找的字符在字符串最后 则T（N）= N
如果查找的字符在字符串中间位置 则T（N）= N/2
这样用大O渐进表示法就要三种情况
情况一： O(1) 情况二： O(N) 情况三： O(N)
这里我们就会发现，有些算法的时间复杂度存在多种情况
最好情况 ： 任意出入规模的最小运行次数（下界）
最坏情况 ： 任意输入规模的最大运行次数（上界）
平均情况： 任意输入规模的期望运行次数
大O渐进表示法在实际情况中一般关注的是算法的上界，也就是最坏运行情况。
所以这里strchr函数的时间复杂度为：O（N）
2.2.5、示例五
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; } }
冒泡排序的时间复杂度
如果数组有序为升序，则T(N) = N （最好情况）
如果数组有序为降序，则T(N) = (N*(N+1))/2 （最坏情况）
因此BubbleSort的时间复杂度为 O(N^2)
2.2.6、示例六
void func4(int n) { int cnt = 1; while (cnt < n) { cnt *= 2; } }
Func4函数
n=2，执行次数为1
n=4，执行次数为2
n=16，执行次数为4
当执行次数为x时，n=2^x
所以执行次数 x= 
所以时间复杂度为： 
这里也可以写成log n
当N接近无穷大时，底数的大小对结果影响不大。因此，一般情况下不管底数为多少都可以省略不写，写成log n
2.2.7、示例七
long long Fac(size_t N) { if (0 == N) return 1; return Fac(N - 1) * N; }
这里每一次调用Fac函数的时间复杂度为O(1)
而一共有n次递归，所以阶乘递归的时间复杂度为O（N）
三、空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中因为算法的需要额外临时开辟的空间
空间复杂度表示程序占用了多少bytes的空间，因为常规情况下每个对象大小 差异不会很大，所以空间复杂度计算的是变量的个数
空间复杂度也使用大O渐进表示法
这里函数运行时所需要的栈空间（存储参数，局部变量。一些寄存器信息等）在编译期间已经确定好了，空间复杂度主要通过函数在运行时显示申请的额外空间来确定
空间复杂度计算
示例一
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; } }
函数栈帧在编译期间已经确定好了，只需关注函数在运行时额外申请的空间
BubbleSort额外申请的空间有exchange等有限个局部变量，使用了常数个额外的空间
因此时间复杂度为：O(1）
示例二
long long Fac(size_t N) { if (N == 0) return 1; return Fac(N - 1) * N; }
Fac递归调用了N次，额外开辟了N个函数栈帧，每个栈帧使用了常数个空间
因此时间复杂度为：O(N)
感谢各位大佬支持并指出问题，
