time-complexity - 算法何时可以具有平方根(n)时间复杂度？

Question

有人可以给我一个具有平方根(n)时间复杂度的算法的例子。平方根时间复杂度甚至意味着什么？

Answer 1

平方根时间复杂度意味着该算法需要 O(N^(1/2)) 次评估，其中输入的大小为 N。

作为一个需要 O(sqrt(n)) 时间的算法的例子，格罗弗的算法就是一个需要那么多时间的算法。 Grover's algorithm 是一种量子算法，用于在 O(sqrt(n)) 时间搜索 n 个条目的未排序数据库。

让我们举个例子来理解，给定一个问题，我们如何才能达到 O(sqrt(N)) 的运行时复杂度。这将是详细的，但理解起来很有趣。 (下面的例子，在回答这个问题的上下文中，取自 Coding Contest Byte: The Square Root Trick ，非常有趣的问题和有趣的技巧，以达到 O(sqrt(n)) 复杂度)

给定 A，包含一个 n 元素数组，实现用于点更新和范围求和查询的数据结构。

update(i, x)-> A[i] := x(点更新查询)

query(lo, hi)-> 返回 A[lo] + A[lo+1] + .. + A[hi]。 (范围和查询)

天真的解决方案使用数组。更新(数组索引访问)需要 O(1) 时间，范围总和需要 O(hi - lo) = O(n)(从开始索引到结束索引迭代并累加)。

更有效的解决方案将数组拆分为长度为 k 的切片并将切片和存储在数组 S 中。

更新需要恒定的时间，因为我们必须更新 A 的值和相应 S 的值。在 update(6, 5) 中，我们必须将 A[6] 更改为 5，这导致 S 的值更改 1使 S 保持最新状态。

range-sum 查询很有趣。第一个和最后一个切片(部分包含在查询范围内)的元素必须一个一个遍历，但是对于完全包含在我们范围内的切片，我们可以直接使用 S 中的值并获得性能提升。

在 query(2, 14) 我们得到，

 query(2, 14) = A[2] + A[3]+ (A[4] + A[5] + A[6] + A[7]) + (A[8] + A[9] + A[10] + A[11]) + A[12] + A[13] + A[14] ; 
 query(2, 14) = A[2] + A[3] + S[1] + S[2] + A[12] + A[13] + A[14] ;
 query(2, 14) = 0 + 7 + 11 + 9 + 5 + 2 + 0;
 query(2, 14) = 34;

更新查询代码为:

  def update(S, A, i, k, x):
      S[i/k] = S[i/k] - A[i] + x
      A[i] = x

  def query(S, A, lo, hi, k):
      s = 0
      i = lo
      //Section 1 (Getting sum from Array A itself, starting part)
      while (i + 1) % k != 0 and i <= hi:
          s += A[i]
          i += 1
      //Section 2 (Getting sum from Slices directly, intermediary part)
      while i + k <= hi:
          s += S[i/k]
          i += k
      //Section 3 (Getting sum from Array A itself, ending part)
      while i <= hi:
          s += A[i]
          i += 1
  return s

现在让我们确定复杂性。

每个查询平均占用

第 1 部分平均需要 k/2 时间。 (你最多可以迭代 k/2)

第 2 节平均需要 n/k 时间，基本上是切片数

第 3 部分平均需要 k/2 时间。 (你最多可以迭代 k/2)

所以，总的来说，我们得到 k/2 + n/k + k/2 = k + n/k 时间。

而且，这对于 k = sqrt(n) 被最小化。 sqrt(n) + n/sqrt(n) = 2*sqrt(n)

所以我们得到一个时间复杂度为 O(sqrt(n)) 的查询。