algorithm - 此代码片段的时间复杂度

Question

最近，我看到了一段代码:

int i = 1;
while (N > 1)
{
        N = N / i;
        i = i + 1;
}

根据观察，很明显 i 线性增加，并且 i 在循环的每个运行时除以 N，因此我们可以说N 减少为阶乘的反函数。

我们如何用theta 表示法 表示它，因为逆阶乘 不是为每个自然数 N 定义的？我们是否必须使用此函数的近似上限和下限来满足要求？

Answer 1

嗯，我不确定，但我会试一试。阶乘本质上是一个 gamma function . Gamma 函数不仅针对自然数定义，还针对实数定义。因此，理论上存在一个反 Gamma 函数，它是为未定义阶乘的情况定义的(例如，我们不知道 5 的反阶乘，但我们知道， 5 的反 Gamma 函数将是两点附近的东西)。根据MathOverflow ，反 Gamma 函数没有精确的公式，但有近似解。

我们假设存在反 Gamma 函数，并将其写为 InvGamma(N)。它是一个实数(可能是 R+，但我不确定，现在它不重要，因为我们的 N 总是正数，除了 N == 0 的情况，我暂时忽略它)。

然后我们可以像使用其他返回实数的函数一样使用它，当我们处理复杂性时:我们可以floor它(向下舍入)。就像我们处理 log 复杂性一样。我曾经使用方括号编写(即 log(15) = 1.18、[log(15)] = 1)。

那么你的代码片段的复杂度应该是 O([InvGamma(N)])，我相信。

更新:(受@6502 的回答启发):请注意，如果 N 是一个整数(代码片段中未提及)，则将进行舍入每一步都以复杂的方式改变复杂性。上面的解决方案适用于真正的 N。