计算大阶乘时间复杂度
Calculating large factorial time complexity
我 运行 遇到了一个问题，我需要计算非常大的阶乘的值。我用两种不同的方式在 C++ 中解决了这个问题，但只想知道我的复杂性分析是否准确。
在这两种方法中，我都将非常大的数字表示为向量，其中 v[0] 表示最低有效数字，最后一个索引处的值表示最高有效数字。可以在 gist.
中找到版本 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! 的向量表示。该函数将 return 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!)) 个步骤。总结如下：
我从第二个求和跳到 Big-Oh 符号的逻辑如下...打破这个我们得到以下内容：
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^2)log(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，很明显我们做了 i-1 加法。我们可以列举前面示例调用我们的简单乘法函数的步骤。
5! + 5!
2*5! + 5!
3*5! + 5!
4*5! + 5!
5*5! + 5!
写出完整的总结现在应该给出：
鉴于我的计算是准确的，这两种方法的渐近复杂度似乎是相同的。这是真的吗？
您提供的要点中函数的复杂度为 O(log<sub>10</sub>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<sub>10</sub>((n-1)!)⌉。你可以从一个简单的例子中看出这一点：
如果(n-1)!为100，则numVector的长度为3，与⌈log<sub>10</sub>相同100⌉ = 3.
同样的逻辑也适用于 while 循环：
while (carry) {
returnVec.push_back(carry%10);
carry /= 10;
}
既然carry的值不会大于n（这个你可以自己证明），那么这个循环的最大次数运行也不会大于⌈log<sub>10</sub>n!⌉，那么函数的总复杂度相当于O(log<sub>10</sub>n!).
因此，要计算k!，你的代码（包括main）的复杂度将是O(klog<sub>10</sub>k!)
朴素的版本
对于原始版本，唯一改变的是现在该方法以加法的形式手动逐步执行乘法。这是另一个版本通过将每个值显式乘以 n
而跳过的内容
(numVector[i]<strong>*n</strong> + 进位)
这将函数的复杂度增加到 O(klog<sub>10</sub>n!)，其中 k! = n 因此整个代码的复杂度现在是 O(k<sup>2</sup>log<sub>10</sub>k!)
将一个 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 因素。
我 运行 遇到了一个问题，我需要计算非常大的阶乘的值。我用两种不同的方式在 C++ 中解决了这个问题，但只想知道我的复杂性分析是否准确。
在这两种方法中，我都将非常大的数字表示为向量，其中 v[0] 表示最低有效数字，最后一个索引处的值表示最高有效数字。可以在 gist.
鉴于上面的代码，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! 的向量表示。该函数将 return 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!)) 个步骤。总结如下：
我从第二个求和跳到 Big-Oh 符号的逻辑如下...打破这个我们得到以下内容：
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^2)log(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，很明显我们做了 i-1 加法。我们可以列举前面示例调用我们的简单乘法函数的步骤。
5! + 5!
2*5! + 5!
3*5! + 5!
4*5! + 5!
5*5! + 5!
写出完整的总结现在应该给出：
鉴于我的计算是准确的，这两种方法的渐近复杂度似乎是相同的。这是真的吗？
您提供的要点中函数的复杂度为 O(log<sub>10</sub>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<sub>10</sub>((n-1)!)⌉。你可以从一个简单的例子中看出这一点：
如果(n-1)!为100，则numVector的长度为3，与⌈log<sub>10</sub>相同100⌉ = 3.
同样的逻辑也适用于 while 循环：
while (carry) {
returnVec.push_back(carry%10);
carry /= 10;
}
既然carry的值不会大于n（这个你可以自己证明），那么这个循环的最大次数运行也不会大于⌈log<sub>10</sub>n!⌉，那么函数的总复杂度相当于O(log<sub>10</sub>n!).
因此，要计算k!，你的代码（包括main）的复杂度将是O(klog<sub>10</sub>k!)
朴素的版本
对于原始版本，唯一改变的是现在该方法以加法的形式手动逐步执行乘法。这是另一个版本通过将每个值显式乘以 n
(numVector[i]<strong>*n</strong> + 进位)
这将函数的复杂度增加到 O(klog<sub>10</sub>n!)，其中 k! = n 因此整个代码的复杂度现在是 O(k<sup>2</sup>log<sub>10</sub>k!)
将一个 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 因素。