algorithm - Count(A, B, n)算法的Big-O(O(n))和Big-Omega(Ω(n))时间复杂度

Question

下面的 Count(A, B, n) 算法的 big-O (O(n)) 和 Big-Omega (Ω(n)) 时间复杂度是多少？

Algorithm Count (A, B, n)

我做了以下事情:算法计数(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”循环。算法 count 执行的最大原语操作数在最坏情况和最好情况下都是 0.5n^2+ n + 1。

Answer 1

我认为最坏的情况是 O(n^2)，而最好的情况是 Ω(1)。最好的情况是你有一个大小为 2 的数组，并且 A[1] >= 0，在这种情况下，算法只需通过循环一次。如果 n 可以为 0(即空数组)，那就更好了。

为了说明最佳情况(n = 2，假设 0 是 Not Acceptable ，并且 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)