为了账号安全,请及时绑定邮箱和手机立即绑定

什么是嵌套循环的Big-O,其中内循环中的迭代次数由外循环的当前迭代确定?

什么是嵌套循环的Big-O,其中内循环中的迭代次数由外循环的当前迭代确定?

PIPIONE 2019-08-28 10:07:46
什么是嵌套循环的Big-O,其中内循环中的迭代次数由外循环的当前迭代确定?以下嵌套循环的Big-O时间复杂度是多少:for(int i = 0; i < N; i++) {     for(int j = i + 1; j < N; j++)     {         System.out.println("i = " + i + " j = " + j);     }}它还是O(N ^ 2)吗?
查看完整描述

3 回答

?
侃侃无极

TA贡献2051条经验 获得超10个赞

是的,它仍然是O(n ^ 2),它具有较小的常数因子,但这不会影响O表示法。


查看完整回答
反对 回复 2019-08-28
?
蓝山帝景

TA贡献1843条经验 获得超7个赞

是。回想一下大-O的定义:O(F(N))由定义说,运行时间T(N) ≤ KF(n)的一些恒定ķ。在这种情况下,步数将是(n-1)+(n-2)+ ... + 0,其重新排列为0到n-1的和; 这是

T(n)=(n-1)((n-1)+1)/ 2

重新排列,你可以看到T(n)总是≤1/ 2(n²); 根据定义,因此T(n)= O(n 2)


查看完整回答
反对 回复 2019-08-28
?
慕斯王

TA贡献1864条经验 获得超2个赞

如果忽略System.out.println,则为N平方。如果你假设它所花费的时间在它的输出中是线性的(当然它可能不是),我怀疑你最终得到O((N ^ 2)* log N)。

我提到这不是挑剔,但只是要指出你在解决复杂性时不仅需要考虑明显的循环 - 你需要考虑你所称的复杂性。


查看完整回答
反对 回复 2019-08-28
  • 3 回答
  • 0 关注
  • 598 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信