最近,我发现了一段代码片段:
int i = 1;
while (N > 1)
{
N = N / i;
i = i + 1;
}
观察得知,变量
i
线性增加且在循环的每一次运行中除以 N
,因此我们可以说 N
是一个阶乘的倒数函数。由于倒数阶乘并非对于每个自然数 N
都有定义,那么我们该如何用 theta 表示法 表达这个问题?我们是否只能使用该函数的上下界来近似表示?最近,我发现了一段代码片段:
int i = 1;
while (N > 1)
{
N = N / i;
i = i + 1;
}
i
线性增加且在循环的每一次运行中除以 N
,因此我们可以说 N
是一个阶乘的倒数函数。由于倒数阶乘并非对于每个自然数 N
都有定义,那么我们该如何用 theta 表示法 表达这个问题?我们是否只能使用该函数的上下界来近似表示? 5 的反阶乘,但我们知道 5 的反伽马函数将在两点左右)。根据MathOverflow的说法,没有反伽马函数的精确公式,但有近似解。
假设反伽马函数存在,并将其写为 InvGamma(N)。它是一个实数(可能是R +,但我不确定,现在不重要,因为我们的N始终是正数,除了N == 0的情况,我现在会忽略它)。
然后,我们可以像使用返回实数的其他函数一样使用它来处理复杂度:我们可以对其进行下取整(向下舍入)。就像我们处理对数复杂度一样。我过去常用方括号来写(即log(15) = 1.18
,[log(15)] = 1
)。
那么你的代码片段的复杂度应该是O([InvGamma(N)])
,我认为。
更新:(受@6502答案启发)请注意,如果N是整数(在代码片段中没有提到),则每个步骤都会进行四舍五入,这会以一种复杂的方式改变复杂度。上面的解决方案适用于实数N。
sqrt
也返回多个值(一个正数和一个负数),但在复杂度函数中仍然被简单地用作O(sqrt(N))
。 - FreeNicknamegamma(n) = (n-1)!
。N
的类型。但我同意,它很可能是某种类型的 整数
。 - FreeNickname