前面说了算法的相关概念以及算法的基本特点（或者说是算法设计的要求），这次来着重说一下算法的所谓“高效性”的衡量方法。
首先我们要提到一个名词叫复杂度，复杂度的意思就是算法从原始数据到目标数据的处理数量的多少的衡量。很绕口是吧，那跳过上一句话不要回去看它了。举个例子：
还是那个讨厌的班主任，给你一份全班同学的成绩表，要你帮他算一下所有人的平均分反正闲着也是闲着。
还好，虽然他比较讨厌，但是这个很好算，先求和，然后除以人数，完成。
然后班主任一看小伙子处理的蛮快的嘛，那好，辛苦你再去算一下方差好了反正闲着也是闲着。。
这个就有一丢丢麻烦了，已经有了平均成绩，然后要用每个人的成绩去减平均成绩，然后把得到的差平方，然后把每一个差的平方加起来，除以人数，完成。
然后班主任一看小伙子处理的蛮快的嘛，那好，辛苦你再去算一下标准差好了反正闲着也是闲着。。。
（画外音：A:我不干了！！！B:那人家想看标准差嘛！）
没办法，只能再对方差求算数平方根，完成。
纵观整个事件，班主任只给了你原数据，然后你一步步求 平均数->求方差->求标准差 的过程，需要进行的操作的一步步增加，也就是算法一步步变复杂的过程。希望大家能从上例中有所启发。
有了复杂度的概念，我们所说的复杂度主要是体现在两个方面的：时间复杂度和空间复杂度
时间复杂度
这里要说到一个名词：原操作
所谓的原操作指的就是基本变量的操作，而有的操作是比较关键的、起主要作用的，这种原操作又称为基本操作 ，在下面的代码例子中会说明。
一条语句重复执行的次数，我们称之为该语句的频度。
来段例子：
for(i=0;i<n;i++) //执行 n次
for(j=0;j<n;j++) //执行 n平方 次
{
c[i][j]=0; //执行 n平方 次
for(k=0;k<n;k++) //执行 n立方 次
c[i][j]=c[i][j]+a[i][k]*b[k][j]; //原操作，执行 n立方 次
}
可以算出来上面的算法一共执行了多少次：
T(n)=2n3+2n2+n
我们得到了该算法的总语句频度，表示方式是一个多项式。
我们把这个多项式的最高项取出来并忽略最高项的常数系数，就得到了该算法的时间复杂度：
O(n3)
对于O(n3)，同样的，还有O(1)、O(n)、O(2n)、O(log2n)、O(nlog2n)等复杂度量级，按照复杂度从小到大排序为：
O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n)
其中，前三种都是可以实现的，但是后三种复杂度在n取值大一些的时候，整个算法的效率就会变得很低，就没有意义了。
算法的复杂度这里，课本上写了很多，最点题的两句：
1.算法时间复杂度取决于最深循环内包涵基本操作的语句的重复执行次数（频度）。
2.讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时间的上限。
空间复杂度
算法的执行过程中需要的存储空间包括以下三个方面：
1.算法块中的各个变量所需要的空间和。
2.所输入的初始数据的额外存储空间。
3.算法执行中需要的额外的空间。
但是如果算法中的变量是取决于问题本身而与算法无关的话，那就不算在内。比如一个交换两个数的算法，我们用的临时变量应该考虑进算法中，而存储原数据的变量是不能算进来的。
类似于时间复杂度，空间复杂度S(n)=O(f(n))
一般来说，时间复杂度和空间复杂度是难以二者兼顾的，我们经常需要牺牲存储上的优势去减小时间复杂度，或者牺牲时间性能去迎合存储的要求。目前各类硬件的发展已经让存储条件不再苛刻，所以，一般来说，常常以算法的执行时间作为算法优劣的主要衡量指标。
才疏学浅，如有错漏，恳请指教，不甚感激。
网友评论