文章目录一、时间频率1 .概念2 .特点2.1常数项忽略2.2低阶项忽略2.3系数二、时间复杂度1 .概念2 .计算时间复杂度3.1常数级o(1) 3.2对数级o(n ) 3.3线性级o(n ) 3.4线性对数级o ) n ) 398；
一、时间频率1 .概念
一个算法所需的时间与算法中语句的执行次数成比例，哪个算法中语句的执行次数多，其所需的时间就多。一个一个算法中的语句执行次数称为语句频度或时间频度，记为 T(n)
例如，要计算1到100之间的所有数字之和，有两种方法： 第一种方式： int total=0； for(intI=1； i=100； I ) {总=I； )其时间频率t(n )=n 1 ) i=101时，for循环再判断一次，因此n 1 )第二方式： int total=0； 总=(1100 ) * 100/2； 其时间频率t(n )=1)2.随着特征程序规模的增大，时间频率有以下三个特点：
常数项忽略低次项忽略系数（n^k (k=3)不适用）2.1常数项忽略可以从下图中看出。
随着程序规模n的增大，t(n )=2n 30和t(n )=2n的执行曲线无线逼近，常数项30可以忽略不计。
2.2忽略低次项，如下图所示。
随着程序规模n的增大，t(n )=2n3n20和t(n )=2n的执行曲线基本一致，低阶项3n 20可以忽略。
2.3忽略系数可以从下图中看出
随着程序规模n的增大，t(n )=3n 2n和t(n )=5n 7n的执行曲线基本一致，系数3和系数5可以忽略。
但是，由于t(n )=n5n和t ) n )=6n 4n进行曲线分离，所以忽略系数不适用于n^k(k=3)的情况。
二、时间复杂度1 .概念一般来说，算法中基本操作语句的重复执行次数是具有问题规模n的函数，用t(n )表示，当n接近无限大时，t(n )/f (n )的极限值有不等于0的常数
2 .计算时间复杂度t(n )不同，时间复杂度可能相同。
例如，t(n )=n ) 27n6和t(n )=3n ) 2n3的t ) n )不同，但是它们的时间复杂度相同，是o(n )2)，可以忽略常数项，可以忽略低次项，可以忽略系数，两者的时间频率都是t(n ) 由于辅助函数f(n )=n ) 2的存在，使得t ) n )/f ) n )=1(不是0的常数)，因此t ) n )=n ) 2n6和t )=3n^2n3的时间复杂度都为o ) f((n
3.1常量级o(1)算法无论执行了多少行代码，只要是没有循环等复杂结构，该算法的时间复杂度为o )1)。
例如，int i=10； int j=20； I； j； int s=i j； 其时间复杂度小于或等于o(1) 3.2对数阶数o(n )，在while循环中，每个循环的I乘以2，循环结束(n次时该代码结束，因此其时间复杂度为o(n )。称 f(n) 是 T(n) 的同数量级函数，记作 T(n) = O(f(n)) ，称 O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
例如，int n=100； int i=1； wile(In ) {i=i * 2； (时间复杂度为o(n ) 3.3的线性阶数o(n )如下，for循环中的代码执行n次，该代码所需的时间随着n的变化而变化，因此时间复杂度为o(n )。
例如，int n=100； int j=1； for(intI=0； i n； I () j； (由于其时间复杂度为o(n ) 3.4线性对数阶o(n，如下所示，内层环的时间复杂度为o(n )，外层环的时间复杂度为o(n )，因此该码的时间复杂度为o(n(*o(n )，即
例如，int n=100； for(intI=0； i n； I({intj=1； while(jn ) { j=j * 2； (其时间复杂度为o(n(3.5平方阶o(n )2)嵌套2层的时间复杂度为o(n )的循环，其时间复杂度为o(n )2)。O(1)O(n)O(n)O(nn)O(n^ 2)O(n^ 3) O(n^ k)O(2^ n)
例如，int n=100； int s=0； for(intI=0； i n； I ) for(intj=0； j n； j () s； }其时间复杂度为o(n )2)4.平均时间复杂度和最差时间复杂度对数阶的底数是基于代码变化的，假设循环中执行的代码为 i = i * 3 则这段代码的时间复杂度为 O(n)。是指所有可能的输入实例均概率出现时算法的执行时间。立方阶和 k 次方阶与之类似。是指最坏情况下算法的执行时间。平均时间复杂度保证算法的运行时间不会比最坏情况更长，因为最坏情况下的时间复杂性限制了算法在任何输入实例上的运行时间。
典型排序算法的时间复杂性：
排序法平均时间复杂度最差时间复杂度冒泡排序o(n ) o(n )交换排序o ) n ) n )选择排序o ) n ) o ) n(n(o(n(s )1s2周期)