一、什么是时间复杂度在计算机科学中时间复杂度又称时间复杂性算法的时间复杂度是一个函数它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。简单定义运行时间T与输入规模n之间的函数关系,T f(n)。用于测量算法在时间方面的效率。时间复杂度常用大O符号表述不包括这个函数的低阶项和首项系数。使用这种方式时时间复杂度可被称为是渐近的亦即考察输入值大小趋近无穷时的情况。二、计算方法。求解算法的时间复杂度的具体步骤是找出算法中的基本语句即算法中执行次数最多的那条语句通常是最内层循环的循环体。计算基本语句的执行次数的数量级用大Ο记号表示算法的时间性能。计算时间复杂度可以将其分为三类:单层循环的时间复杂度计算两层循环的时间复杂度计算多层循环的时间复杂度计算1、单层循环的时间复杂度计算步骤:列出循环趟数t及每趟循环i的变化值。找到t与i的关系。确定循环停止条件。联立两式解方程。写结果最大数量级。i n * n; while (i ! 1) i i/2;2、两层循环的时间复杂度计算步骤:列出外层循环中i的变化值。列出内层语句的执行次数。求和写结果。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)
