1

我试图找出下面给定代码的复杂性作为问题大小 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 语句将是块 1 或块 2。因为O(logn)它比 sum ++ 慢，所以O(1)它是O(logn)。所以它是O(n)*O(logn)。

因此，最终答案将是O(1) + n*O(logn)。这个对吗？？

4

2 回答 2

2

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

于 2012-10-09T18:31:04.263 回答
0

是的，O(nlog(n)) 将是复杂性。

于 2012-10-09T18:38:05.793 回答