转载自：https://www.jianshu.com/p/1ac6ad4069f8
算法的选择
我们都知道同一个问题有不同的算法解决，这些算法在运行时间、运行占用内存、代码易读性等方面都不相同，而在这些算法中，我们只能选择一种解决方案，这时判断选择哪个算法的依据是什么呢？
在这里，我们引入了时间复杂度和空间复杂度这两个概念作为选择适合算法的重要依据，一般对比算法的好坏基本上从它的时间复杂度和空间复杂度来综合判断就可以得出哪个更适合，复杂度通常来说越小越好。
算法的时间复杂度和空间复杂度的作用：时间复杂度是指执行这个算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。时间和空间（即寄存器）都是计算机资源的重要体现，而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少。
时间复杂度 （Time complexity）
一个算法语句总的执行次数是关于问题规模N的某个函数，记为f(N)，N称为问题的规模。语句总的执行次数记为T(N)，当N不断变化时，T(N)也在变化，算法执行次数的增长速率和f(N)的增长速率相同。
则有T(N) = O(f(N))，这称作算法的渐进时间复杂度，简称时间复杂度。
1、算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好地反映出算法的优劣与否。
2、算法执行时间需要依据该算法编制的程序在计算机上执行运行时所消耗的时间来度量，度量方法有两种：事后统计方法和事前分析估算方法。因为事后统计方法更多地依赖计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣，因此常采用事前分析估算的方法。
3、一个算法是由控制结构（顺序、分支、循环三种）和原操作（固有数据类型的操作）构成的，而算法时间取决于两者的综合效率。
4、一个算法花费的时间与算法中语句的执行次数成正比，执行次数越多，花费的时间就越多，其执行次数称为语句频度或时间频度，记为T（n）。
5、在时间频度中，n为问题的规模，当n不断变化时，它所呈现出来的规律，我们称为时间复杂度。
6、在各种算法中，若算法中的语句执行次数为一个常数，则时间复杂度为o（1），同时，若不同算法的时间频度不一样，但他们的时间复杂度却可能是一样的。比如：T(n)=n^2+2n+4 与 T（n）=4n^2+n+8，他们的时间频度显然不一样，但他们的时间复杂度却是一样的，均为O(n^2)，时间复杂度只关注最高数量级，且与之系数也没有关系。
最坏时间复杂度和平均时间复杂度
最坏情况下的时间复杂度称最坏时间复杂度，一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间，设每种情况的出现的概率为pi,平均时间复杂度则为sum(pi*f(n)) 。
求解算法的时间复杂度的具体步骤
⑴ 找出算法中的基本语句
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
⑶ 用大Ο记号表示算法的时间性能
将基本语句执行次数的数量级放入大Ο记号中，如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体；如果算法中包含并列的循环，则将并列循环的时间复杂度相加。
下面举一个简单例子：
for(i=1;i<=n;i++)
{a++};
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
a++;
}
}
第一个for循环的时间复杂度为o（n），第二个for循环时间复杂度为o（n^2），则整个算法的时间复杂度为o(n^2+n)。
o(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，时间复杂度就为o(1)。
时间复杂度的分析方法
1、时间复杂度就是函数中基本操作所执行的次数
2、一般默认的是最坏时间复杂度，即分析最坏情况下所能执行的次数
3、忽略掉常数项
4、关注运行时间的增长趋势，关注函数式中增长最快的表达式，忽略系数
5、计算时间复杂度是估算随着n的增长函数执行次数的增长趋势
6、递归算法的时间复杂度为：递归总次数 * 每次递归中基本操作所执行的次数
7、常用的时间复杂度有以下七种，算法时间复杂度依次增加：O(1)常数型、O(log2 n)对数型、O(n)线性型、O(nlog2n)二维型、O(n^2)平方型、O(n^3)立方型、O(2^n)指数型.
特殊时间复杂度
1.二分查找
因为每次的计算，都可以把查找的范围缩小一半，所以二分查找的时间复杂度为O（log2 N)。
2.斐波那契的递归算法
因为每次的展开都要把当前的已知项再拆分成当前数目的两倍，所以斐波那契的递归算法时间复杂度为2^N。
斐波那契的时间复杂度算法如下图所示，计算n第N个斐波那契数的大小时，共需计算2^N - 1次。
常用排序算法的时间复杂度
空间复杂度（Space Complexity）
一个程序的空间复杂度是指运行完一个程序所需内存的大小，利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。
（1）固定部分：这部分空间的大小与输入/输出的数据的个数多少、数值无关，主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间，这部分属于静态空间。
（2）可变空间：这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等，这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。
1、空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
2、一个算法在计算机上占用的内存包括：程序代码所占用的空间、输入输出数据所占用的空间、辅助变量所占用的空间这三个方面。程序代码所占用的空间取决于算法本身的长短，输入输出数据所占用的空间取决于要解决的问题，是通过参数表调用函数传递而来，只有辅助变量是算法运行过程中临时占用的存储空间，与空间复杂度相关。
3、通常来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为0(1)。
4、算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题的规模没有关系。
特殊空间复杂度
在斐波那契数求空间复杂度的过程中，我们需要考虑函数栈帧的过程，比如当我们求第五个斐波那契数的时候，这时候需要先开辟空间存放第四个数，然后再开辟空间存放第三个数；当开辟空间到第二个和第一个数的时候，第三个数得到结果并返回到第四个数中，第四个数的值已知后返回到第五个数中，在这个过程中，最大占用空间即为层数减一。如下图所示：
开辟空间的大小最多等于层数+1，也就是说求第N个斐波那契数，空间复杂度即为O（N）。
二分查找因为整个运算过程没有空间的改变，所以空间复杂度为O（1）。
时间复杂度与空间复杂度的联系
对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间;反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。
1、求二分法的时间复杂度和空间复杂度
非递归：
templateT* BinarySearch(T* array,int number,const T& data)
{
assert(number>=0);
int left = 0;
int right = number-1;
while (right >= left)
{
int mid = (left&right) + ((left^right)>>1);
if (array[mid] > data)
{
right = mid - 1;
}
else if (array[mid] < data)
{
left = mid + 1;
}
else
{
return (array + mid);
}
}
return NULL;
}
分析：
循环的基本次数是log2N，所以，时间复杂度是O(log2N);
由于辅助空间是常数级别的，所以，空间复杂度是O(1)。
递归：
templateT* BinarySearch(T* left,T* right,const T& data)
{
assert(left);
assert(right);
if (right >=left)
{
T* mid =left+(right-left)/2;
if (*mid == data)
return mid;
else
return *mid > data ? BinarySearch(left, mid - 1, data) : BinarySearch(mid + 1, right, data);
}
else
{
return NULL;
}
}
分析：
递归的次数和深度都是log2N,每次所需要的辅助空间都是常数级别的：
时间复杂度:O(log2N)
空间复杂度：O(log2N )
2、斐波那契数列的时间和空间复杂度
//递归情况下的斐波那契数列
long long Fib(int n)
{
assert(n >= 0);
return n<2 ? n : Fib(n - 1) + Fib(n-2);
}
递归的时间复杂度是： 递归次数*每次递归中执行基本操作的次数，所以，时间复杂度是： O(2^N)。
递归的空间复杂度是： 递归的深度*每次递归所需的辅助空间的个数，所以，空间复杂度是：O(N)。
//求前n项中每一项的斐波那契数列的值
long long *Fib(int n)
{
assert(n>=0);
long long *array = new long long[n + 1];
array[0] = 0;
if (n > 0)
{
array[1] = 1;
}
for (int i = 2; i
循环的基本操作次数是n-1,辅助空间是n+1，所以：
时间复杂度O(n)
空间复杂度O(n)
//非递归
long long Fib(int n)
{
assert(n >= 0);
long long first=0,second=1;
for (int i = 2; i <= n; i++)
{
first = first^second;
second = first^second;
first = first^second;
second = first + second;
}
return second;
}
循环的基本次数是n-1，所用的辅助空间是常数级别的：
时间复杂度：O(n)
空间复杂度：O(1)
总结
对于一个算法，算法的时间复杂度和空间复杂度往往是相互影响的，其所有性能之间都存在着或多或少的相互影响，因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性、算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。
作者：Java资讯库
链接：https://www.jianshu.com/p/1ac6ad4069f8
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 标签：递归,复杂度,次数,算法,时间,详细,空间,解说 From： https://www.cnblogs.com/zhncnblogs/p/17522895.html