java - 你如何找出七次搜索的大 O 和大 Omega？

Question

在家庭作业中，我们得到了一个叫做“七分搜索”的东西，它类似于二分搜索，但不是将数据结构减半，而是将其分割为 7 组。我们被要求通过编写递归方程并求解它来证明最坏情况下的运行时间在 BigTheta(log n) 中。

这是七次搜索的伪代码:

septenarySearch(L, s):
  HELPER(L, 0, L.length-1, s)

HELPER(L, Lo, Hi, s):
  if Hi - Lo + 1 > 7:
    basic_group_size = floor((Hi - Lo + 1) / 7)
    number_of_larger_groups = (Hi - Lo + 1) % 7
    for i in 0 .. 6:
      group_size = basic_group_size
      if i < number_of_larger_groups:
        group_size = group_size + 1
      first_element_of_group = i*group_size
      last_element_of_group = (i+1)*group_size - 1
      if L[first_element_of_group] <= s <= L[last_element_of_group]:
        return HELPER(L, first_element_of_group, last_element_of_group, s)
  else:
    for index in Lo .. Hi:
    if s == L[index]:
      return true
    return false

我们还得到提示，考虑的元素数量 递归调用HELPER中至少有1/7传入的范围(Lo和Hi之间)，且数量不超过1/4。

我很确定其中一个递归方程是 T(n) = c + T(n/7) 其中 c 是某个常数值，我认为这让我 BigO(log n)。如果我试图证明 Big Theta，我也需要证明 BigOmega(log n)，对吗？我如何找到 BigOmega 是什么？

我确定 1/4 应该用于查找 BigOmega，但不确定如何执行此操作(甚至不知道 1/4 从何而来)。

Answer 1

给出的提示:

Number of elements in recursive call >= n/7                     (+)
Number of elements in recursive call <= n/4                     (++)

因此，算法运行时间的下限和上限由下式给出

Lower bound: 
Assume all recursive calls contains n/7 number of elements from
range passed to previous call call (n elements). 
Recurrence relation: 

     T_L(n) = T(n/7) + c                                        (i)

Upper bound: 
Assume all recursive calls contains n/4 number of elements from
range passed to previous call call (n elements). 
Recurrence relation:  

     T_U(n) = T(n/4) + c                                        (ii)

您可以通过展开递归来解决 (i) 和 (ii)，这将直接为您提供 Big-Θ 关系:

现在你被问及最坏情况下的复杂度，在这种情况下 T(n) = T_U(n)。因此，最坏的情况是T(n) ∈ Θ(log_4 n)。