计算大阶乘的时间复杂度

Question

计算大阶乘的时间复杂度

c++algorithmtime-complexityfactorialasymptotic-complexity

10

我遇到了一个问题，需要计算非常大的阶乘值。我用 C++ 用两种不同的方式解决了这个问题，但我只想知道我的复杂度分析是否准确。

在任一方法中，我将非常大的数字表示为向量，其中v[0]表示最不重要的数字，最后一个索引处的值表示最重要的数字。版本1的代码可以在此代码片段中找到。

根据上述代码，似乎multiplyVectorByInteger()是O(log(n*k))，其中n是给定的整数，k是由向量表示的数字。我的逻辑是，我们将执行与产生表示n*k的向量成比例的长度的一些步骤，以便表示n*k。 n*k的长度是O(log(n*k))。一些步骤将在for循环中执行，其他步骤将在随后的while循环中执行。

在此程序中，为了查找大阶乘，每当我们调用multiplyVectorByInteger()时，我们将传入整数n和(n-1)！的向量表示。这意味着如果我们要找到6！，我们传入整数6和5！的向量表示。该函数将返回6！的向量表示。使用之前的信息，我相信我可以说复杂度为O(log(i!))，其中i是传入的整数。为了找到大的阶乘，我们必须调用此方法O(n)次，其中n是我们要查找的阶乘。

1!       = 1!
1!*2     = 2!
2!*3     = 3!
3!*4     = 4!
...
(n-1)!*n = n!

由于每一层我们都要计算i!，因此在每一层上执行O(log(i!))步骤。展示这一点的求和公式如下：

sum1

我从第二个求和符号跳到大O符号的逻辑如下...将其拆分，我们得到以下内容：

1log(1) + 2log(2) + 3log(3) + ... + nlog(n)

很明显，我们可以得到log(1)+log(2)+...+log(n)的O(n^2)项。对数法则提醒我们，log(a)+log(b)=log(ab)，这意味着在这种情况下，对数项会合并为log(n!)。因此，我们有O(n^2log(n!))。

这将使该程序的总时间复杂度为O(n^2log(n!))。这个分析正确吗？

朴素版本时间复杂度

为了练习复杂性分析，我想看一下似乎不那么高效的解决方案。假设我们改变我们的multiplyVectorByInteger()函数，使它不再以O(log(n!))的时间将k的向量表示乘以整数n来生成n!，而新的multiplyVectorByIntegerNaive()函数将一个数字的向量表示相加共计n次。

multiplyVectorByIntegerNaive()在这个gist中。它使用一个addVectors()函数，其复杂度为O(n)，其中n是两个向量中较大的那个的大小。

很明显，我们仍然调用这个新的乘法函数n次，但我们需要看看复杂度是否发生了变化。例如，给定整数6和5!的向量表示，我们将5!+5!+5!+5!+5!+5!相加，以得到6*5!=6!。如果要将给定的整数传递给我们的乘法函数，则很明显我们要进行i-1次加法。我们可以枚举针对先前示例调用朴素乘法函数的步骤。

5! + 5!
2*5! + 5!
3*5! + 5!
4*5! + 5!
5*5! + 5!

现在写出完整的求和式应该是：

sum2

根据我的计算，这两种方法的渐近复杂度相同。这是真的吗？

- Dominic Farolino

你在第一个案例中的分析过于悲观了。显然，\sum_{i=0}^n (log i!) <= n*log n!，你怎么会得到 n^2 呢？ - n. m.

将数字存储为整数确实是一种浪费。字节或半字节就足够了。但当然，计算和进位必须使用整数完成。 - user1196549

关于您的第一条评论，看看我在哪里写了第一个求和符号，然后说 ~从第二个求和到大O的逻辑如下...似乎那个 i乘以log(i)的系数产生了(n*(n+1))/2项，这是O(n^2)，这就是为什么我有一个 n` 的系数。 - Dominic Farolino

@MartinBonner，性能问题并不是一个问题，虽然我感谢你的评论。这只是一个纯粹的复杂性分析实践。我喜欢缓存的想法，可能会成为一个很好的动态规划算法。 - Dominic Farolino

@YvesDaoust 关于你最后的评论，我试图看一下为什么会有额外的因子n。显然我的分析是错误的，但是如果你看一下我在写出第一个求和之后的陈述，从第二个求和跳到大O符号的逻辑是... 你能告诉我这里有什么问题吗？简而言之，似乎有(n*(n+1))/2个log(i)的项。由于log(i)的求和等于log(n!)，似乎应该是O(n^2log(n!))，但正如你所说，这里有些问题。 - Dominic Farolino

显示剩余10条评论

2个回答

1

将一个k位数乘以一个整数或将两个k位数相加，所需的时间都与k成正比。

因此，在乘法版本中，总工作量为

Sum[i=1,n]: log(i!) ~  Sum[i=1,n]: i.log(i) ~ n²log(n)

在添加版本中，

Sum[i=1,n]: i.log(i!) ~ Sum[i=1,n]: i².log(i!) ~ n³.log(n)

这些结果可以通过使用斯特林逼近和积分而不是求和来确定。

Int x.log(x) dx = x²(log(x)/2 - 1/4)
Int x².log(x) dx = x³(log(x)/3 - 1/9)

正如预料的那样，这里有一个额外的 n 因素。

- user1196549

似乎我的错误在于我说的那个语句中：Sum[i=1,n]: i.log(i) = O(n^2log(n!)。每个人都说我多乘了一个因子n，但我想不出为什么。您能否在我画出第一项求和式后直接查看我的陈述，并指出那种逻辑上的错误呢？ - Dominic Farolino

@DomFarolino：“很明显我们得到O(n^2)个log(1)+log(2)+...+log(n)的项”：也许对你来说是，但对我来说不是。 - user1196549

好的，那很公平，你能解释一下为什么我的分析是错误的吗？看起来我们得到了log(1) + log(2) + log(2) + log(3) + log(3) + log(3)等等。这样做有问题吗？ - Dominic Farolino

@DomFarolino：你是怎么得出这是O(n²Log(n!))的结论的？ - user1196549

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- smac89 · Accepted Answer

您提供的代码片段中函数的复杂度为O(log₁₀n!)，其中n是传递给该方法的数字。

这个推理显而易见，从代码的第一部分可以看出：

for (int i = 0; i < numVector.size(); ++i) {
    returnVec[i] = (numVector[i]*n + carry) % 10;
    carry = (numVector[i]*n + carry) / 10;
}

传入的numVector表示(n-1)!，即包含组成该数字的所有数字。但是该数字的长度仅为⌈log₁₀((n-1)!)⌉。您可以从一个简单的例子中看到这一点:

如果(n-1)!为100，则numVector的长度将为3，与⌈log₁₀100⌉ = 3相同。

同样的逻辑也适用于while循环。

while (carry) {
    returnVec.push_back(carry%10);
    carry /= 10;
}

由于carry的值不会大于n（您可以自行证明），因此此循环运行的最大次数也不会大于⌈log₁₀n!⌉，则该函数的总复杂度等同于O(log₁₀n!)。

因此，要计算k!，您的代码复杂度（包括主函数）将为O(klog₁₀k!)。

朴素版本

对于朴素版本，唯一改变的是现在该方法通过加法手动遍历乘法。其他版本通过将每个值显式乘以n来跳过此步骤。

(numVector[i]*n + carry)

这将使函数的复杂度增加到O(klog₁₀n!)，其中k!=n，因此整个代码的复杂度现在为O(k²log₁₀k!)。