（新手上路）疑问：for循环如何计算时间复杂度

93 阅读 0 评论 62 点赞

我是靠谱客的博主甜美星星，最近开发中收集的这篇文章主要介绍（新手上路）疑问：for循环如何计算时间复杂度，觉得挺不错的，现在分享给大家，希望可以做个参考。

看到这样一段代码：

for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
//复杂度为O(1)的算法
...
}
}

这个算法的时间复杂度为什么是O（n^2）呢？

观察内循环

n+(n-1)+(n-2)+(n-3)+……+1
=(n+1)+[(n-1)+2]+[(n-2)+3]+[(n-3)+4]+……
=(n+1)+(n+1)+(n+1)+(n+1)+……
=(n+1)n/2
=n(n+1)/2

=n²/2+n/2

我们可以得到内循环的时间复杂度为O（n²），为什么不再乘以外循环的n呢？

关键：

如果内外循环之间的循环量之间没关系可将内外循环次数之积作为复杂度看待

若有关系则考虑内循环的基本操作的执行次数来分析复杂度

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。