回答
最内圈将明显运行j
次。假设它包含价值100个单位时间的操作,这将是:
T_inner(j) = j
环路中间将运行i
倍,即
T_middle(i) = Sum {j from 1 to i} T_inner(j)
= Sum {j from 1 to i} j
= i/2 * (1 + i)
最后:
T_outer(n) = Sum {i from 1 to n} T_middle(i)
= Sum {i from 1 to n} (i/2 * (1 + i))
= 1/6 * n * (1 + n) * (2 + n)
= 1/6 n^3 + 1/2 n^2 + 1/3 n
这显然是O(n^3)
。
注意:这只会计算最内侧块中的操作。它忽略了执行循环所需的操作。但是如果你包含这些,你会发现时间复杂度是一样的。
谢谢! @NicoSchertler,它的工作原理:) –
所以通常当算法的复杂性被讨论时,他们是否考虑循环所需的操作,还是它总是被忽略? –
维护循环所需的操作将始终与迭代次数(加上初始化操作)成比例。所以,这与向内部块添加恒定量相似。最终,这并不会改变复杂性。 –
- 1. 这段代码片段的时间复杂度是多少?
- 2. 这个程序片段的时间复杂度是多少?
- 3. Collection.toArray()的时间复杂度是多少?
- 4. 下面的代码片段O(n^2)的时间复杂度是多少?
- 5. 减少时间复杂度
- 6. 给定代码的时间复杂度?
- 7. 分时排序算法的时间复杂度是多少?
- 8. 我的代码中的时间复杂度是多少
- 9. AngularJS的脏检查算法的时间复杂度是多少?
- 10. NavigableMap的floorEntry()方法的时间复杂度是多少?
- 11. 这个算法(代码)的时间复杂度是多少?
- 12. 代码的时间复杂度是多少?
- 13. 梅森扭纹机的时间复杂度是多少?
- 14. 这个函数的时间复杂度是多少?
- 15. 这个伪代码的时间复杂度是多少?
- 16. java中StringBuilder.append()的时间复杂度是多少?
- 17. 这个算法的时间复杂度是多少?
- 18. 以下代码的时间复杂度是多少?
- 19. Python中zip()的时间复杂度是多少?
- 20. clojure中count函数的时间复杂度是多少?
- 21. DataRow索引器的时间复杂度是多少?
- 22. C++中std :: next_permutation()函数的时间复杂度是多少?
- 23. 这个循环的时间复杂度是多少?
- 24. 树遍历的时间复杂度是多少?
- 25. Python中collections.Counter()的时间复杂度是多少?
- 26. 密码散列函数的时间复杂度是多少?
- 27. 搜索JavaScript对象键的时间复杂度是多少?
- 28. TreeSet中有序操作的时间复杂度是多少?
- 29. 迭代std :: set/std :: map的时间复杂度是多少?
- 30. Java中LinkedList.getLast()的时间复杂度是多少?
你在这个问题上做了什么工作?例如,你可以说明'j'的复杂性和确切的公式吗?有关'k'的确切公式,使复杂性变得很明显,请参阅[四面体数字](https://en.wikipedia.org/wiki/Tetrahedral_number)。 –
看起来像n^3。虽然我在时间复杂性方面非常糟糕,所以我可能是错的。而且,这些标签中的大部分都是不相关的。 – byxor
我已经按照建议移除了标签。 @BrandonIbbotson –