用于求和大量非常大的算法(C )

Question

我正在尝试解决问题13 @ project euler，我正在寻找一种良好的算法来做添加，并为大量数字输出答案。首先，我将数字的数字转换为矩阵(100 x 50(的元素。这是我想到的算法：

unsigned long long int sum=0, carry_over=0;
for(int j=49; j>=0; j--)
{
    for(int i=0; i<100; i++)
        sum+=num[i][j];
    sum+=carry_over;
    carry_over=sum/10;
    cout<<sum%10;
    sum=0;
}
cout<<carry_over;  

现在，输出将具有逆转数字，从单位放置位置，最终以总和的第一个数字结束。这很容易手动逆转。

我想知道这是否是一种很好的算法，考虑到准确性和速度。请提出更正以改善它。

Answer 1

您的算法已经是最佳的。

您的算法具有O(m*n)的时间复杂性，其中m是每个数字(50(中的数字数(50(和n是数量(100(的数量(100(，这就是您输入中的数字数量。很容易看出您必须读取 all 为了输出正确的答案，因此您必须至少读取m*n数字，从而给出O(m*n) 的时间复杂性用于阅读输入。因此，您的算法的时间复杂性不能少于此，因此您的O(m*n)算法是最佳的。

如果以某种方式，您已经有RAM中的输入数据(以及合适的格式(，则可以考虑其他一些优化。

地址大小的考虑：

现代计算机的地址大小为32或64位，这意味着它们可以在一个操作中对32或64位进行添加。64位约为18个小数位，因此存储每个整数所需的3个64位整数，因此，添加的时间复杂性将从m=50降低到m=3，从而使总和更快。p>并行处理：

现代计算机可以并行运行多个线程。解决此问题的解决方案很容易平行。如果您的计算机能够同时运行2个线程，则可以使用第一个线程和第二个线程使用前50个数字。两次总和完成后(如果在单个线程上计算所有内容，则大约是所需的一半(，您只需总和两个子重点。