此代码片段的时间复杂性

Question

最近,我遇到了一个代码片段:

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

在观察时,很明显i线性地增加,并且在循环的每个运行时间中i分开N,因此我们可以说它N作为因子的反函数的函数而减小.

我们如何用theta表示法表示这一点 ,因为没有为每个自然数定义反因子N？我们是否必须使用此函数的近似上限和下限？

Answer 1

好吧，我不确定，但我会尝试一下。阶乘本质上是伽玛函数。并且gamma函数不仅针对自然数定义，也针对实数定义。因此，理论上存在一个反伽玛函数，它是针对阶乘未定义的情况定义的（例如，我们不知道 的反阶乘5，但我们知道 的反伽玛函数5将是大约两点）。根据MathOverflow 的说法，逆伽玛函数没有精确的公式，但有近似解。

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

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

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

更新：（受到@6502的答案的启发）：请注意，如果N是一个整数（代码片段中没有提到），那么每个步骤都会进行舍入，这会以复杂的方式改变复杂性。上面的解决方案适用于 real Ns。