这段代码片段的时间复杂度

Question

最近，我发现了一段代码片段：

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

观察得知，变量 i 线性增加且在循环的每一次运行中除以 N，因此我们可以说 N 是一个阶乘的倒数函数。由于倒数阶乘并非对于每个自然数 N 都有定义，那么我们该如何用 theta 表示法 表达这个问题？我们是否只能使用该函数的上下界来近似表示？

- shauryachats

---

5的阶乘逆元是多少？@FreeNickname - shauryachats

抱歉，我的错。我误解了你的意思。由于某种原因，我认为1/n！是一个倒数阶乘。我现在会删除我的评论。 - FreeNickname

你也可以尝试在Math Stack Exchange上提问。告诉他们你有计算机科学背景。我发现他们非常乐于助人。（仅仅是为了明确：我并不是说这个问题在这里不合适） - bolov

Answer 1

好的，我不确定，但我会尝试一下。 阶乘本质上是伽马函数。伽马函数不仅适用于自然数，也适用于实数。因此，在理论上存在一个反伽马函数，它定义了阶乘未定义的情况（例如，我们不知道 5 的反阶乘，但我们知道 5 的反伽马函数将在两点左右）。根据MathOverflow的说法，没有反伽马函数的精确公式，但有近似解。

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

然后，我们可以像使用返回实数的其他函数一样使用它来处理复杂度：我们可以对其进行下取整（向下舍入）。就像我们处理对数复杂度一样。我过去常用方括号来写（即log(15) = 1.18，[log(15)] = 1）。

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

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

- FreeNickname

---

伽玛反函数实际上是让人信服的。感谢。不过唯一的缺点是返回多个值。 - shauryachats

@ShauryaChats，是的，确实如此。解决方法是取最大值。不幸的是，我不确定应该使用什么符号来正确地表示它。我想我会把它留在原地。在我看来，它很清楚它的意思。例如，sqrt也返回多个值（一个正数和一个负数），但在复杂度函数中仍然被简单地用作O(sqrt(N))。 - FreeNickname

Answer 2

"自然的"阶乘推广到除了负整数以外的所有复平面上被称为"伽马函数"，在所有非负整数上，gamma(n) = (n-1)!。

因此，您可以反转gamma的一部分来计算所需的迭代次数的近似值，但我不确定这是否会导致像那个代码中每一步都有舍入操作的"精确"计算迭代次数。请注意，要保留HTML标记。"

- 6502

---

每一步都进行舍入操作的观点很好。不过我们不知道 N 的类型。但我同意，它很可能是某种类型的 整数。 - FreeNickname

@FreeNickname 浮点数运算也会导致舍入！ - Rerito

@Rerito，是的，它会，但通常在复杂度计算中忽略浮点算术舍入，否则我们将无法计算一半算法的复杂度。 - FreeNickname