algorithm - 依赖随机结果终止的算法的最坏情况时间复杂度？

Question

假设我们有一个递归函数，它仅在随机生成的参数满足某些条件时才终止:

例如:

{
define (some-recursive-function)

    x = (random in range of 1 to 100000);
    if (x == 10)
    {
        return "this function has terminated";
    }
    else
    {
        (some-recursive-function)
    }
}

我知道对于无限循环，不会定义复杂性。一些肯定终止但在未知时间后终止的函数呢？

为此找到平均时间复杂度就可以了。如果存在的话，人们将如何找到最坏情况下的时间复杂度？

提前致谢!

编辑:正如一些人所指出的，我完全忽略了这个函数没有输入的事实。相反，假设我们有:

{define (some-recursive-function n)

    x = (random in range of 1 to n);
    if (x == 10)
    {
        return "this function has terminated";
    }
    else
    {
        (some-recursive-function)
    }
}

这会改变什么吗？

Answer 1

如果没有 n 的函数从上面限制函数的运行时间，那么就没有运行时间的上限。视情况而定，运行时间可能有下限。我们还可以谈论预期的运行时间，甚至对预期的运行时间设置界限，但这一方面不同于平均情况的界限，另一方面不同于运行时间本身的界限。

正如目前所写的那样，当 n 小于 10 时根本没有界限:该函数在任何情况下都不会终止。对于 n >= 10，在任何情况下仍然没有上限 - 它可能需要任意长的时间才能完成 - 但在任何情况下下限都低至线性(您必须至少读取 n 的值，它由 N = ceiling(log n) 位组成；您选择不大于 n 的随机数的方法可能需要额外的时间和/或空间)。这里的案例行为相当无趣。

如果我们根据输入的值(而非长度)考虑函数的预期运行时间，我们会观察到任何特定调用都有 1/n 的机会选择正确的随机数(同样，对于 n > = 10);我们认识到，我们需要尝试获得一个的次数由几何分布给出，并且期望为 1/(1/n) = n。因此，预期的递归深度是输入值 n 的线性函数，因此是输入大小的指数函数 N = log n。我们恢复了期望的精确表达式；因此，上限和下限也是线性的，这涵盖了所有情况(最好、最差、平均等)。我说递归深度，因为运行时还有一个额外的因素 N = log n，或更多，由于上一段中的观察。