我想找到下面代码的时间复杂度。这是我的理解-
外部 for 循环将循环 2n
次,在最坏的情况下,当 i==n
时,我们将进入 if block ,其中嵌套 for 循环的复杂度为O(n^2)
,算上外层for循环,代码块的时间复杂度为O(n^3)
。
在最好的情况下,当 i!=n
时,else 的复杂度为 O(n)
,外部 for 循环的复杂度为 O(n)
> 这使得复杂性增加,在最好的情况下为 O(n^2)
。
我是正确的还是我在这里遗漏了一些东西?
for (int i = 0; i < 2*n; i++)
{
if (i == n)
{
for (int j = 0; j < i; j++)
for (int k = 0; k < i; k++)
O(1)
}
else
{
for (int j = 0; j < i; j++)
O(1)
}
}
最佳答案
没有。
问题“什么是 T(n)?”。 你的意思是“如果 i=n,则 O(n^3),否则 O(n^2)”。 但问题里没有 i,只有 n。
想一个类似的问题: “一周内,皮特周三工作 10 小时,每隔一天工作 1 小时,皮特一周工作总时间是多少?”。 你并没有真正回答“如果本周是星期三,则 X,否则 Y”。 您的答案必须包括周三和每隔一天的工作时间。
回到你原来的问题,星期三是 i=n 时的情况,所有其他日子都是 i!=n 时的情况。 我们必须将它们全部总结起来才能找到答案。
关于algorithm - 带 if-else block 的 for 循环的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/66352165/