Count（A、B、n）アルゴリズムのBig-O（O（n））およびBig-Omega（Ω（n））時間の複雑度

Question

big-Oカウント値Nの点で下記（A、Bは、N）アルゴリズムのオメガ（Ω（n））を時間の複雑Algorithm Count (A, B, n)

Iた以下

： アルゴリズムカウント（A、B、N）

Input: Arrays A and B of size n, where n is even. 
      A, B store integers.               # of operations: 
     i <- 0                         1 
     sum <- 0                        1 
     while i < n/2 do                    n/2 + 1 
       if A[i + n/2] < 0 then                n/2 + 1 
        for j <- i + n/2 to n do             n/2 + n/2+1 + … + n = n(n+1)/2 
         sum <- sum + B[j]               n/2 + … + n = n(n+1)/2 
       i <- i + 1                      n/2 + 1 
     return sum                     _ _1______  

アルゴリズムカウントは、O（n^2）およびΩ（n^2）のBig-OおよびBig-Omegaで実行されます。このアルゴリズムは、ネストされた「for」ループを含む。アルゴリズムカウントによって実行されるプリミティブ操作の最大数は、最悪の場合と最善の場合の両方で0.5n^2+ n + 1です。

Answer 1

ベストケースはΩ（1）ですが、最悪の場合はO（n^2）だと思います。最適なケースは、サイズ2の配列を持ち、A [1]> = 0の場合です。この場合、アルゴリズムはループを一度通過するだけです。 nが0（つまり空の配列）の場合、それはさらに優れています。

最高のケース（n = 2、0は受け入れられず、A [1]> = 0）を説明するために、割り当て操作に一定の時間C1がかかるとします。

i <- 0 
sum <- 0 

は一定時間2 * C1をとります。

while 0 < 2/2 do 

は一定時間C2を要する。

if A[0 + 2/2] < 0 then //evaluates to false when A[1] >= 0 

は一定時間C3を要し、ネストされたforループは決して実行されない。

i <- i + 1 

は一定時間C4を要する。ループは不変をチェックします：

while 1 < 2/2 do 

これはC2になります。その後、操作は次のように戻ります。

return sum 

これはC5になります。

だから、最良のシナリオでの操作ここで、n = 2およびAは、[1]> = 0は、次のとおりです。

2*C1 + 2*C2 + C3 + C4 + C5 = O(1) 

さて、あなたはそれがされている必要があることを主張することができます。

2*C1 + (n/2 + 1)*C2 + C3 + C4 + C5 = O(n) 

しかし私たちはすでに最高でn = 2であることを知っています。これは一定です。最良のシナリオでは、n = 0である場合には

：

2*C1 + C2 + C5 = O(1)