算法 时间复杂度
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了算法 时间复杂度,现在分享给大家,供学习和参考。文章包含2386字,纯文字阅读大概需要6分钟。
教程信息
一、时间复杂度的表示方法
1、假设算法的输入规模为n,其执行时间是T(n),算法随着n扩大而增加的趋势是一个函数f,满足T(n)=f(n)
——以该定义计算时间复杂度【每个基本操作的执行时间粗略标记为 unit_time】
int cal(int n) { // 1次定义 1*unit_time int sum = 0; // 1次定义,n次判断,n次自增 1*unit_time+n*unit_time+n*unit_time for (int i = 1; i <= n; ++i) { // n次循环(每次1次定义,n次判断,n次自增) n*(1*unit_time+n*unit_time+n*unit_time+n*unit_time) for (int j = 1; j <= n; ++j) // n次循环(每次n次累加) sum = sum + i * j; // n次赋值 n*unit_time j = 1; } }
T(n)
=1*unit_time+(1*unit_time+n*unit_time+n*unit_time)+n*(1*unit_time+n*unit_time+n*unit_time+n*unit_time)+n*unit_time
=(3n2+4n+2)*unit_time
2、上述1的方法,这样表示时间复杂度过于繁琐,因此引入渐进符号大O,用一个简单函数去描述复杂函数。T(n)=O(f(n))
(1)找出执行次数最多、时间占比最大的操作,作为考量的“基本操作”
(2)计算基本操作的执行次数,常数、非最高次项忽略
int cal(int n) { int sum = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) sum = sum + i * j; // n次循环(每次n次累加) j = 1; } }
T(n)=O(f(n))=O((3n2+4n+2)*unit_time)=O(n2)
二、时间复杂度的运算规则
1、加法法则
顺序程序的总复杂度,等于量级最大的那段代码的复杂度。
2、乘法法则
嵌套代码的总复杂度,等于嵌套内外代码复杂度的乘积。
3、循环法则
(1)只需关注循环次数最多的那段代码。
(2)循环次数和n之间的关系一般包括:次数与n无关、次数即n、次数是log2n(每次减少一半)。
4、多参数法则
(1)有两个参数控制两个并列循环的次数,那么这时就取二者复杂度相加O(f(m) + g(n))
(2)有两个参数控制两个嵌套循环的次数,那么这时就取二者复杂度相乘O(f(m) *g(n))
5、递归法则
递归函数的时间复杂度是“递归的次数 * 每次递归中的操作次数”
三、时间复杂度的上下限
1、最好情况时间复杂度
输入数据最优情况下的时间复杂度,往往是算法的下限(需要至少这么长的时间)
2、最坏情况时间复杂度
输入数据最劣情况下的时间复杂度,往往是算法的上限(需要至多这么长的时间)
3、平均情况时间复杂度
输入数据的所有可能情况下,时间复杂度的加权平均值
(1)平均情况时间复杂度通常比最坏情况时间复杂度更能反映算法的执行效率。
(2)平均情况时间复杂度也更难计算,通常需要使用概率和统计方法进行分析。
四、常见的时间复杂度
1、常数阶O(1)
算法的执行时间不随数据规模增加而增加(算法的执行时间是固定的)
int add(int a, int b) { return a + b; }
2、对数阶O(log n)
算法的执行时间随数据规模呈对数增长(数据规模增加一倍,执行时间增加一个常数时间)
let i=1; while (i <= n) // 执行次数是2的指数级别的缩减,输入参数n越大的时候,体现的优势越大。 i = i * 2;
3、线性阶O(n)
算法的执行时间随数据规模呈线性增长(数据规模增加一倍,执行时间增加一倍)
let i=1; while (i <= n) // 执行次数和输入参数n呈现1:1的关系。 i = i++;
4、线性对数阶O(nlog n)
算法的执行时间随数据规模呈 nlogn 增长
function aFun(n){ let i = 1; while (i <= n) i = i * 2; return i } // 汇总:O(nlog n) function cal(n) { let sum = 0; // 循环:n for (let i = 1; i <= n; ++i) // 自定义函数:logn sum = sum + aFun(n); return sum; }
5、乘方阶O(nk)
算法的执行时间随数据规模呈nk增长
int cal(int n) { int sum = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) sum = sum + i * j; j = 1; } }
6、指数阶O(kn)
算法的执行时间随数据规模呈kn增长(随着数据规模的增长,算法执行时间暴增,几乎不存在)
7、阶乘阶O(n!)
算法的执行时间随数据规模呈n!增长(随着数据规模的增长,算法执行时间暴增,几乎不存在)
性能开销示意图(爬升越快的开销越大)
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供算法 时间复杂度的全部内容,希望教程文章能够帮你了解学习算法 时间复杂度,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaozhongji-255.html