以下算法的时间复杂度是多少？
for(i=0;i< m; i++)
{
for(j=i+1; j < m; j++)
{
for(k=0; k < n;k++)
{
for(l=0;l< n;l++)
{if(condition) do something}
}
}
}
for(i=0;i< m; i++)
{
for(j=i+1; j < m; j++)
{
for(k=0; k < n;k++)
{
for(l=0;l< n;l++)
{if(condition) do something}
}
}
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
详细信息：
前两个循环将导致 (m-1) + (m-2) + (m-3) + ... + 1 次重复，等于 m*(m-1)/2。至于后两个循环，它们基本上从 0 运行到 n-1，因此需要 n^2 次迭代。
由于你不知道条件是否会被满足，所以你会采取最坏的情况，即它总是被满足。
那么迭代次数为：
m*(m+1)/2*n^2*NumberOfIterations(Something)
在 O 表示法中，常数和更低的次数不是必需的，因此复杂度为：
O(m^2*n ^2)*O(某事)
In details:
The two first loops will result in (m-1) + (m-2) + (m-3) + ... + 1 repetitions, which is equal to m*(m-1)/2. As for the second two loops, they basically run from 0 to n-1 so they need n^2 iterations.
As you have no clue whether the condition will be fulfilled or not, then you take the worst case, which is it being always fulfilled.
Then the number of iterations is:
m*(m+1)/2*n^2*NumberOfIterations(Something)
In O notation, the constants and lower degrees are not necessary, so the complexity is:
O(m^2*n^2)*O(Something)
内部循环将运行
((m-1) + (m-2) + ... 1)次在这种情况下，内部循环显然运行
n * n 次很明显，迭代次数恰好是 显然
，这假设
如果（条件）做某事以恒定时间运行。
The inner loop will run
((m-1) + (m-2) + ... 1)timesIn this case, the inner loop clearly runs
n * n timesSo clearly, the number of iterations is exactly
Obviously, this assumes that
if(condition) do somethingruns in constant time.
对我来说看起来像 O(m^2 n^2) ，假设“某事”是恒定时间的。
尽管
j循环每一步都从不同的点开始，但i和j循环的综合效果仍然是 m^2 因子。评估未声明的条件本身通常（至少）是一个恒定时间操作，因此循环肯定不能比 O(m^2 n^2) 更快 - 当然，除非“某事”包括中断、转到、异常抛出或任何提前退出一个或多个循环的内容。
如果出于某种原因，n 或 m 在整个过程中不是恒定的，那么所有的赌注都会失败。
Looks like O(m^2 n^2) to me, assuming the "something" is constant-time.
Although the
jloop starts from a different point with each step, the combined effect of theiandjloops is still an m^2 factor.Evaluating the unstated condition itself would normally be (at least) a constant time operation, so certainly the loop cannot be faster than O(m^2 n^2) - unless, of course, the "something" includes a break, goto, exception throw or whatever that exits out of one or more of the loops early.
All bets are off if, for any reason, either n or m isn't constant throughout.
我假设“做某事”的时间复杂度是 O(S)。
让我们从最内层的循环开始：它的时间复杂度是 O(n*S)，因为它做了 n 次。包裹最内层循环的循环的时间复杂度为 O(n)O(nS)=O(n^2*S)，因为它执行了内层循环 n 次。
包含第二个最内部循环的循环的时间复杂度为 O(mi)*O(n^2*S)，因为它执行 O(n^2*S) 操作 mi 次。
现在对于更难的部分：对于 0...m-1 范围内的每个 i，我们执行 (mi)*O(n^2*S) 操作。多久时间？ (1 + 2 + 3 + ... + m)*O(n^2*S)。
但是 (1 + 2 + ... + m) 是一个算术序列的总和。因此总和等于 m*(m-1)/2=O(m^2)。
结论：我们执行了大约 m^2 次 O(n^2*S) 操作。整个事情的时间复杂度是 O(m^2*n^2*S)
I assume the time complexity of "do something" is O(S).
Let's start with the most inner loop: It's time complexity is O(n*S) because it does something n times. The loop which wraps the most inner loop has a time complexity of O(n)O(nS)=O(n^2*S) because it does the inner loop n times.
The loop whcih wraps the second most inner loop has a time complexity of O(m-i)*O(n^2*S) because it does an O(n^2*S) operation m-i times.
Now for the harder part: for each i in the range 0...m-1 we do an (m-i)*O(n^2*S) operation. How long does it take? (1 + 2 + 3 + ... + m)*O(n^2*S).
But (1 + 2 + ... + m) is the sum of an arithmetic sequence. Therefore the sum equals to m*(m-1)/2=O(m^2).
Conclusion: We do an O(n^2*S) operation about m^2 times. The time complexity of the whole thing is O(m^2*n^2*S)
O(m^2*n^2*(某物的复杂性))。如果条件和某些内容在恒定时间内执行，则 O(m^2*n^2)。
O(m^2*n^2*(compexity of something)). If condition and something are executed in constant time then O(m^2*n^2).
O(m²*n²) *“某物”的复杂性
O(m²*n²) *complexity of "something"