确定 for 循环的时间复杂度
我知道这个循环的复杂度是 O(n^2)，但是 Big-Omega 和 Big-Theta 是什么？在这种情况下你如何计算它们？
for(i = 0; i < array.length; i++)
for (j = 0; j < array.length; j++)
//bla bla
I know that this loop is O(n^2) but what is Big-Omega and Big-Theta? How do you go about calculating them in situations like these?
for(i = 0; i < array.length; i++)
for (j = 0; j < array.length; j++)
//bla bla
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对于初学者，请参阅拉斯曼的评论。循环逻辑不一定微不足道到可以排除。为了便于论证，假设您确信循环逻辑不会被破坏，逻辑很简单（即没有条件路径影响所执行的工作），并且您将工作单元定义为通过循环一次执行的总逻辑。
在这种情况下，您的上限和下限是相同的。保证您至少执行、最多执行 N^2 个工作单元。您有一个
Ω(N^2)和一个O(N^2)。您的下限和上限是相同的；您可以表征θ(N^2)。值得再次提及的是，如果循环逻辑非常重要并且特别依赖于您实际定义为工作单元的内容，那么这是毫无意义的。这些符号的目的是描述算法所需的预期工作量。您可以迭代循环数百万次，但是如果您真正关心的工作是在该循环中调用
SomeExpectiveFunction()次数，那么这不会影响此表示法循环，逻辑表明它只被调用一次。For starters, see larsmans' comment. The loop logic is not necessarily trivial enough to exclude. Let's say for argument's sake that you're confident that the loop logic will be not break out, that the logic is trivial (i.e. no conditional paths affecting the work performed), and that you are defining your unit of work to be the total logic performed in one pass through the loop.
In this case, your upper and lower bounds are the same. You are guaranteed to execute at least, and at most, on the order of N^2 units of work. You have a
Ω(N^2), and aO(N^2). Your lower and upper bounds are identical; you can characterizeΘ(N^2).It bears mentioning again that this is pointless if the loop logic is non-trivial and is especially dependent on what you are actually defining as a unit of work. The point of these notations is to characterize an expected amount of work to be incurred by an algorithm. You can iterate through a loop millions of times, but that doesn't affect this notation if the work you really care about is how many times
SomeExpensiveFunction()is called within that loop, and the logic dictates that it is only called once.