证明算法的大哦等

Question

我正在学习如何 prove/disprove big-Oh、big-Omega 和 little-oh，并且我有以下算法 f(n)。但是我不确定如何证明这个 f(n) 因为它有一个我以前从未遇到过的 if 语句。例如，我如何证明这个 f(n) 是 O( n^2 )?

if n is even
  4 sum(n/2,n)
else
  2n-1 sum(n−3,n)

其中 sum(j,k) 是从 j 到 k 的整数的“部分算术和”，即 sum(j,k)=

if j > k
   0
else
   j+(j+1)+(j+2)+...+j

例如sum(3,4) = 3 + 4 = 7 等请注意 sum(j,k) = sum(1,k) – sum(1,j-1).

Answer 1

好的。得到它不用担心。我会尽力帮助您理解这一点。

大 O 表示法用于定义程序在其输入大小方面将花费多少时间的上限。

让我们试试看这个函数中每条语句需要多少时间

f(n) {
  if n is even     // O(1) .....#1
    4 * sum(n/2,n) // O(n) .....#2
  else  // O(1) ................#3
    (2n-1) * sum(n−3,n) // O(n) .......#4
}

if n is even 这可以通过像 if ((n%2) == 0)) 这样的检查来完成，正如您所看到的，这是一个恒定时间的操作。没有循环什么都没有只是一次计算。

sum(j, k) 函数是通过在 j <= k 时从 j 迭代到 k 来计算的。所以，它将运行 (k - j + 1) 次，即线性时间

因此，总复杂度将是 if 块或 else 块的复杂度之和为了分析复杂性，需要考虑最坏的时间。 if 块的复杂度 = #1 + #2 = O(1) + O(n) = O(n)
同样对于 else 块 = #3 + #4 = O(1) + O(n) = O(n) 两者的最大值 = maximum of(O(n), O(n)) = O(n)

因此，整体复杂度 = O(n)

证明算法的大哦等

proving the big-oh etc for an algorithm

algorithm

big-o

time-complexity