1

我总是难以分析随机算法的运行时间。如果有人可以向我解释这一点，我将不胜感激。

以我编写的以下代码为例；

它检查数组中至少出现 n/4 次的元素。（n 是数组的大小）。它从数组中选择一个随机数，检查它是否出现 n/4 次。如果是，它会返回它。否则它会删除所有出现的元素并继续。

假设数组中至少有一个这样的元素至少出现 n/4 次。

elements_left = n ;

    frequency ( A[] )
      {
        k -> pick a random element from A[] ;
        int count = 0;
        int delete_count = 0;

        for (i=0 ; i < elements_left ; i++)
          {  
            if (a[i] = k)
                count++ ;
          }

        if (count >= n/4)
            return A[i] ;
            exit ;

        else
          {
            for (i=0 ; i < elements_left ; i++)
              {  
                if (A[i] = k)
                    delete (A[i]) ;
                    delete_count ++ ;
              }

            elements_left = n - delete_count ;
          }

        frequency (A[])
      }

该算法的最坏情况运行时间和预期运行时间是多少，您将如何得出它？

谢谢。

4

2 回答 2

3

考虑这一点的一种方法如下：在算法的每次迭代中，您将做 O(n) 工作来检查您随机选择的元素是否是您想要的元素。如果是这样，你就完成了。如果没有，您需要做一些工作来从数组中删除该元素的所有其他副本。您上面的伪代码并没有真正指定您如何删除它们（我不知道这意味着删除单个数组元素），但我假设运行时是 O(n)，因为可以删除那个时间元素的所有副本。

现在的问题是，按照预期，需要多少轮才能找到元素？由于该元素有 1/4 的概率被选中，因此预计需要 4 次尝试才能找到它。每次尝试都会做 Θ(n) 工作 - 总元素数总是在 n/4 和 n 之间 - 因此运行时间将是期望值 Θ(n) （Θ(n) 工作的四次迭代。）

希望这可以帮助！

于 2013-10-30T04:26:51.157 回答
2

templatetypedef 的答案描述了一个元素出现 n/4 次的情况。

最坏情况的运行时间是 O(n^2)，如果所有项目都是唯一的，就会发生这种情况。

平均情况很难确定。假设数组包含 100 个项目。除了一个出现 15 次之外，所有的都是唯一的。因此，您必须进行至少 40 次递归调用才能删除足够的项目，以使该单个项目作为结果返回。但是在第一次迭代中，您将有 15/100 的机会删除最常见的项目。下一次有 15/99 的机会等。很有可能（几乎可以肯定）当您进行 40 次选择时，您会选择最常见的项目并将其从数组中删除。

所以，如果你知道有一个元素出现 n/4 次，那么预期的运行时间是 O(n)。否则运行时间高度依赖于项目的分布，最坏情况下的运行时间为 O(n^2)。

于 2013-10-30T13:52:00.797 回答