网页游戏网站建设今日热搜新闻头条

（1）时间频度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

一个方法执行一次需要时间10秒或者多少秒，那么执行n次的总时间，那就n乘以 10，弄个数学公式 10 x n = total time，

10 这个值是固定的，就像去买菜，菜的单价是固定的，多少钱一斤。变化的值是你要买多少斤。

总数 T(n)，一个数学公式： T(n) = n * X；就是关于一个变量n的一阶表达式，简单的数学吧。

计算机里面针对的就是一个总的执行时间 = 关于一个变量执行次数的函数。

常见的就是一层for循环：  T(n) = n * X；循环n次，每次执行时间X。

（2）时间复杂度
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，（就是上面说的概念了）

若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)  /   f(n)   的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

记作：T(n)   =   O(f(n))， 称  O(f(n))  为算法的渐进时间复杂度，简称时间复杂度。

实际举例子：

继续使用上面的常见的一层for循环举例。

T(n) = n * X +5; （X 是执行一次循环体需要的时间，加个5可能是在执行for循环之前需要花费5的时间去做点初始化的事情。）      

当 n 趋近于无穷大的时候，T(n) 的大小就和后面的5 无关了，

基本就可以看成 T(n) = n * X  （X 是常量）为了方便看，直接把X 换成6吧，T(n) = n * 6

现在再来一个关于n的函数 f(n)，使得   T(n)   /    f(n)   =   常量，这里就是 6，那么函数 f(n) = n;

T(n)  /  f(n)  =  (n * 6 )   /   n   =   6 

按照上面的名次解释，T(n)  = O(f(n))  =  O(n)  ;

一层for循环的时间复杂度就是O(n)；

y = ax + b；

想想高中时候，这个函数的图是怎么画的，xy轴的二维图里面，一条斜着向上的直线。

 T(n)  =  n * X +5;

不会高中数学的，咱现场分析一下，当 n 无穷大的时候，后面的5，就忽略不计，n无穷大，T(n)也就无穷大。

对 T(n) 求极限值的公式就等价于  T(n)  =  n * X；

同理分析下面的这个带平方的公式。

T(n)  =  4n²  -  2n  + 2

在 T(n) = 4n²  - 2n + 2中，对T(n)的值求极限，在n无穷大的时候，上面的公式，就等价于 T(n)  =  4n²

就有 f(n) = n²，使得  T(n)  /  f(n)  的极限值为4，那么

 T(n)  = O(f(n)) = O(n²)，

也就是时间复杂度为   O(n²)

咱常见的时间复杂度是 O(n²)的代码实例，一般都是2层for循环。

想想简单的2层嵌套for循环，假设里外都执行n次，那么整个嵌套for循环执行完，是不是得执行n²次里面的循环体

T(n) = n² * X + 10;  执行一次循环体需要X秒，再给10秒的时间初始化一下准备工作。

那么这个f(n) 是不是就 n² ; 也就是说显而易见的 f(n) = n²; 

使得  T(n)  /  f(n)  的极限值为 X

 T(n)  = O(f(n)) = O(n²)，

这个也是成立的。

y =ax² + bx +c

想想高中的图

上面说了O(n)和O(n²)，这个O(1),怎么理解。有何常见的例子吗？

O(1)，说来也简单，也就是说这个的执行时间是不随着次数的增加而增加的，一般比如好多的单利模式，都只是初始化一次，然后一直的被使用。应该算是O(1)的例子吧。

至于下面说的其它的例子，那么复杂的时间复杂度，我就无招了。