java - 给定代码的复杂性？

Question

我试图找出下面给定代码的复杂性作为问题大小 n 的函数。

sum = 0;

if (EVEN(n))
    for (i = 0; i < n; i++)
      if (i%2 == 0)
        O(logn)
      else
        sum ++;
else
    sum = sum + n;

这是我的答案，但我不确定我是否正确。

sum=0; is equal to O(1) .

第一个 if else 循环由一个嵌套的 for 循环和一个嵌套的 if 语句组成。所以这将是 for 循环内代码的 n 倍。因为它的 if 语句 and 将是 block 1 或 block 2。因为 O(logn)比 sum++ 慢，即 O(1)它是O(logn) 。所以是O(n)*O(logn) .

因此最终答案是 O(1) + n*O(logn) 。这是正确的吗？

Answer 1

是的，如果您谈论的是最差运行时间，那么似乎是正确的。您可以将 O(n)*O(logn) 重写为 O(n*log(n))。