**
算法的时间复杂度和空间复杂度
**
1.算法效率
2.时间复杂度
3.空间复杂度
1.算法效率
算法的基本概念：算法是对特定问题求解步奏的一种描述，它是指令的有限序列，其中每一条指令表示多个操作。其中，具有以下五个特性：
1.有穷性，
2.确定性，
3.可行性，
4.输入，
5.输出，
通常一个好的算法应该考虑以下目标：
1）正确性：算法应该正确的求解问题
2）可读性：应该具有良好的可读性
3）健壮性：当输入非法时，算法也可以适当的作出反应或者处理，而不会产生莫名其妙的输出结果
4）效率与低存储量需求：效率是指算法执行的时间，而存储量需求是指算法执行过程需要的最大存储空间。
**
2.时间复杂度
时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法
的时间复杂度。
**
例如：在数组A[0…N-1],查找给定值k的算法大致如下：
1.i=n-1
2.while(i>=0&&(A[i] !=k)
3. i–
4.return i
此算法中的语句（3)（基本运算）的频度不仅与问题规模有关，还与输入实例中 A 的元素取值及 k 的取值有关：
①若 A 中没有与 k 相等的元素，则语句（3）的频度 f ()。
②若 A 的最后一个元素等于 k ，则语句（3）的频度 f ( n ）是常数0。最坏时间复杂度是指在最坏情况下，算法的时间复杂度。
平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。最好时间复杂度是指在最好情况下，算法的时间复杂度。
一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。
在分析一个程序的时间复杂性时，有以下两条规则：
a ）加法规则
T ( n )=T1( n )+T2( n )=0( f ( n ))+0( g ( n ))-0( max ( f ( n ), g ( n ))) b ）乘法规则
T ( n )=T1( n )xT2( n )-0( f ( n ))x0( g ( n ))=0( f ( n ) xg ( n ))常见的渐近时间复杂度有：
O1)<0( logzn )< O ( n )< O (nlog2n)<0( n ')<0( n ')<0(2")<0( n !)
常见时间复杂度计算举例：
1.
void Func2(int N) { int count = 0; for (int k = 0; k < 2 * N ; ++ k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); }
基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为 O(N)
void Func3(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(N+M)
count=0； for(k=1; k<=n; k*=2) for(j=1; j<=n; j++) count++;
内层循环j<=n与外层循环变量无关，每次循环j自增1，每次内层循环次数执行n次，外层条件为 k ≤ n ，增量定义为 k *=2，可知循环次数为2的k次方≤ n ，即 k ≤ logn 。所以内层循度是 O ( n )，外层循环的时间复杂度是 O ( logn )。对于嵌套循环，根据乘法规则可知，时间复杂度 T ( n )= T ( n )T2( n )= O ( n ) O (log2n)=0(nlog2n)
// 计算阶乘递归Fac的时间复杂度？ long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-1)*N; }
通过计算分析发现基本操作递归了N次，时间复杂度为O(N)。
**
3.空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数，空间复杂度计算规则基本跟实践复杂度类似
**常见时间复杂度计算举例：
1.
// 计算阶乘递归Fac的空间复杂度？ long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }
递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)
// 计算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; } }
使用了常数个额外空间，所以空间复杂度为 O(1)
