→时间复杂度
无编辑摘要 |
（→时间复杂度） |
||
第25行：
最简单，也是初学者最常用的一种算法就是看这个算法循环了几层数据规模。设数据规模为 <math>N</math>，假如一个算法只是对几个数进行了简单的运算，它的时间效率跟 <math>N</math> 的大小没有半毛钱关系，那么称这种算法的时间复杂度是 <math>O(1)</math> 的，是所有算法中效率最高的一种。又假如一个算法它从 <math>1-N</math> 遍历了一遍，时间效率跟 <math>N</math> 的大小成正比，那么称这种算法的时间复杂度是 <math>O(N)</math> 的，又称为线性复杂度（因函数 <math>y=x</math> 的图像是一条直线而得名）。再假如一个算法从 <math>1-N</math> 遍历了一遍，每次遍历的时候又从 <math>1-N</math> 遍历了一遍，时间效率跟 <math>N^2</math> 的大小成正比，那么称这种算法的时间复杂度是 <math>O(N^2)</math> 的，以此类推。
顺便一说，时间效率有时候也是可以超过渐进上界复杂度的，重点在于复杂度中的常数。我们刚才列出的时间复杂度都是单纯的字母量，但程序实际运行时往往这个字母量前面会有常数系数，甚至会带有次数更低的字母（比如说 <math>T(N^2+N)</math>）。所以就专门有一个符号 <math>T</math>，指程序实际上的时间复杂度，用 <math>T</math> 的时候可以带有常数和低次的字母。但在大 <math>O</math> 记号中这些通常都被省略不写，因为数据规模很大，常数的数量级很小，往往可以忽略不计。
时间复杂度也有很多玄学的算法。比较容易理解的一种说法就是，算法的时间效率跟数据规模的什么运算成正比，时间复杂度就用数据规模的什么运算表示，比如常见的还有 <math>O(\sqrt{N})</math>，<math>O(\log N)</math>（因为可以用换底公式转化成常数，所以底数通常也省略不写），<math>O(2^N)</math>，<math>O(N!)</math> 等。
| |||