概率算法的时间复杂度

Question

游戏很简单：程序必须 'guess' 一些给定的 n 使得 1 < n < N，其中 n 和 N 是正整数。假设我正在使用真正的随机数生成器函数 ( rng() ) 来生成计算机的 'guess'，它在任何尝试中 'guess' 给定 n 的概率是 1/N。

示例伪代码：

n = a // we assign some positive integer value to n

N = b // we assign some positive integer value to N

check loop
{
   if rng(N) = n
      print some success message
      exit program
   else 
      back to the beginning of the check loop
}

好的，我对如何确定该算法的时间复杂度（尤其是上限）很感兴趣？我有点困惑。概率方面如何影响这一点？如果我没理解错的话，最坏的情况（理论上）是程序永远运行下去？

Answer 1

即使理论上您的程序可以永远运行，这里的复杂性是 O(n) - 因为将 n 加倍，您猜测每个特定值的概率就会减半步骤，从而使步骤数加倍。即使程序可以运行 forever 给定 n，它也会运行 twice forever 如果 n 大 2 倍。

O 表示法的复杂性并没有告诉您将执行多少操作。它告诉您操作数如何取决于输入大小。

概率算法的时间复杂度

Time complexity of probabilistic algorithm

probability

time-complexity