java - 使数组中的每个元素都等于最大元素的复杂性分析

Question

作为问题大小 n 的函数，给定代码的复杂度是多少？显示分析的详细信息。

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)
    }
}

到目前为止我的想法：

if 语句并不总是正确的（可能是 log n）嵌套的内部 for 循环是 n^2。

任何有关如何解决它或如何继续它的帮助将不胜感激。

谢谢你。

标签： javaalgorithmfor-looptime-complexitybig-o

Answer 1

没有if(i == n) {}，操作次数为 ：

1 + 2 + 3 + 4 + 5 + ... + n*2

= (2n * (2n-1))/2

但是在 处i==n，操作次数i不像其他的那样，它是i²。所以最终的操作数是：

((2n * (2n-1))/2) - n + n²

上面的大 O 表示法是 O(n²)