计算大阶乘时间复杂度

Question

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

在任何一种方法中，我都将非常大的数字表示为向量，其中v[0]表示最低有效数字，最后一个索引处的值表示最高有效数字。版本1的代码可以在这个要点中找到。

给定上面的代码，似乎multiyVectorByENTger（）是O（log（n*k））其中n是给定的整数，k是向量表示的数字。我的逻辑是，我们将执行一些与结果数字n*k的长度成比例的步骤，以便生成一个表示n*k的向量。n*k的长度是O（log（n*k））一些步骤将在for循环中执行，其他步骤将在接下来的while循环中执行。

在这个寻找大阶乘的程序中，每当我们调用multiyVectorByENTger（）时，我们都会传入一个整数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！））步骤。显示这一点的总和如下：

我从第二个求和跳到大哦符号的逻辑如下...打破这一点，我们得到以下结果：

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

很明显，我们得到了log（1）log（2）的项。。。对数（n）。日志规则提醒我们，Log（a）Log（b）=Log（ab），这意味着在这种情况下，日志项折叠为Log（n！） 。因此，我们得到了O（n^2）log（n！） 。

这将使该程序的总体时间复杂度为O（n^2log（n！）） 。这个分析正确吗？

为了实践复杂性分析，我想看看什么是效率较低的解决方案。假设我们更改我们的multiplyVectorByInteger（）函数，使其不是将k的向量表示乘以O（log（n！）中的整数 生产时间，新的函数multilyvectorbyintegernave（）将数字的向量表示相加，总计为n次。

multilyvectorbyintegernave（）存在于本要点中。它利用了一个函数，其复杂度为O（n），其中n是两个向量中较大者的大小。

很明显，我们仍然调用这个新的乘法函数n次，但是我们需要看看复杂度是否发生了变化。例如，给定整数6和向量表示5！我们添加5! 5! 5! 5! 5! 5！以获得6*5！=6！。如果我们的乘法函数的给定整数是i，很明显我们做了i-1加法。我们可以枚举前面示例调用朴素乘法函数的步骤。

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

现在写出完整的总结应该给出：

鉴于我的计算是准确的，这两种方法的渐近复杂度似乎是相同的。这是真的吗？




Answer 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因子。

Answer 2

匿名用户

您提供的gist中函数的复杂性为O（log_{10n！），其中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）！。即它包含构成该数字的所有数字。然而，该数字的长度只是log10（（n-1)!)⌉ 。您可以从一个简单的示例中看到这一点：

如果（n-1）！为100，则numVector的长度为3，与log10100=3相同。

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

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

由于携带的值不会大于n（你可以自己证明这一点），那么这个循环运行的最大次数也不会大于log10n！，那么函数的总复杂度相当于O（log10n！）。

因此，要计算k ，代码（包括main）的复杂度将为O（klog<10

对于朴素版本，唯一改变的是现在该方法以加法的形式手动步进乘法。这是另一个版本通过显式将每个值乘以n而跳过的

（numVector[i]*n进位）

这将函数的复杂度增加到O（klog_{10n！） ，其中k！=因此，整个代码的复杂度现在是O（k^{2log10k！）}}