时间复杂度计算方法（简略）_时间复杂度怎么算

//纯新手，第一次学习写博客。

 

一、什么是时间复杂度？

• 名词解释

在计算机科学中，时间复杂度，又称时间复杂性，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。（百度百科）

• 简单定义

简单定义为名词解释的总结，方便记忆。

运行时间T与输入规模n之间的函数关系,T=f(n)。用于测量算法在时间方面的效率。（来自ppt）

二、计算方法。

• 求解算法的时间复杂度的具体步骤是：

1.找出算法中的基本语句：即算法中执行次数最多的那条语句，通常是最内层循环的循环体。
2.计算基本语句的执行次数的数量级；
3.用大Ο记号表示算法的时间性能。

• 计算时间复杂度可以将其分为三类:

①单层循环的时间复杂度计算

②两层循环的时间复杂度计算

③多层循环的时间复杂度计算

（1）单层循环的时间复杂度计算

步骤:
1.列出循环趟数t及每趟循环i的变化值。
2.找到t与i的关系。
3.确定循环停止条件。
4.联立两式，解方程。
5.写结果（最大数量级）。

[例].  i = n * n ;

        while （i ！= 1 ）

              i = i/2 ;

 

 （2）.两层循环的时间复杂度计算

步骤:
1.列出外层循环中i的变化值。
2.列出内层语句的执行次数。
3求和，写结果。

[例].  int m = 0，i，j;

         for （ i = 1; i <= n; i++）

              for （j = 1; j <= 2*i; j++）

                   m++;

 （3）.多层循环的时间复杂度计算

[例].  for( i = 0;i <= n; i++）

             for（ j = 0; j <= i; j++）

                  for（ k = 0; k < j; k++）

方法1:抽象为三维立体图计算体积

 

方法二:求和

计算出每层循环次数，再相乘。

 三、常见时间复杂度。

O(1): Constant Complexity 常数复杂度
O(log n):Logarithmic Complexity 对数复杂度
O(n):Linear Complexity 线性时间复杂度
O(n^2): N square Complexity 平方
O(n^3): N cubic Complexity 立方
O(2^n): Exponential Growth 指数
O(n!): Factorial 阶乘

 

时间复杂度从小到大排序：

O(1) < O(logn) < O(n) ＜ O(nlogn) ＜ O(n^2) ＜ O(n^3) ＜ O(2^n) ＜ O(n!) ＜ O(n^n)