嵌套循环的运行时间 [英] Run time of nested loops
本文介绍了嵌套循环的运行时间的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
对不起,如果已经问过这个问题,我不确定如何搜索.
Sorry if this question has already been asked, I wasn't sure how to search for it.
假设您有以下循环
for (i=0; i < n; i++)
for(j = i; j < n; j++)
这是O(n ^ 2)还是O(nlog(n)),为什么?
Would this be O(n^2) or O(nlog(n)) and why?
推荐答案
外循环的运行时间(本身)为O(n),内循环的运行时间为O(n-i).因此,循环的时间为(n)(n-i),当您丢弃常数i时,运行时间将为O(n ^ 2).
The outer loop's runtime (by itself) is O(n), and the inner loop's runtime is O(n-i). So the loop's time would be (n)(n-i), and when you throw away the constant i, the runtime would be O(n^2).
这篇关于嵌套循环的运行时间的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文