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

最初のifelseループは、ネストされたforループと、ネストされたifステートメントで構成されます。したがって、forループ内のコードはn倍になります。そのifステートメント以降、ブロック1またはブロック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))。

Answer 2

はい、O（nlog（n））が複雑になります。