乘法的算法复杂度

Question

在这被指责为重复之前，我在 Whosebug 上到处寻找这个答案，但未能找到可以向我解释的东西，所以请先完整阅读。

假设您需要编写一个函数，它接受一个整数 n 和 returns 1..n 的正整数之和（我将使用 C）。

int sum_of_integers(int n) {
    int i, counter = 0;
    for(i = 1; i <= n; i++)
        counter += i;
    return counter;
}

显然，这个算法的时间复杂度为 O(n)，因为它运行的指令数与输入大小 n 成正比。

然而，考虑这个实现，使用 1+...+n = (n)(n+1)/2 的数学真理。

int sum_of_integers(int n) {
    //Trying to avoid potential int overflow
    //And take into account int division
    if(n % 2 == 0)
        return (n/2)*(n+1);
    return ((n+1)/2)*n;
}

我的问题： 因为乘法在技术上是大 O > O(n)，第一个实现是首选吗？第二种实现算不算O(1)？

对我来说，因为相同的操作执行相同的次数，所以对于第二个实现，n 的大小无关紧要，所以我觉得它应该在 O(1) 中。另一方面，第二种实现实际上可能是运行基于乘法运算符实现的更多指令。

Answer 1

教科书乘法需要时间 O(b^2) 其中 b 是数字中的位数，因此使用公式 n(n+1)/2 需要时间 O((log n)^2) 这比 O(n) 快得多。

乘法的算法复杂度

Algorithmic Complexity of Multiplication

c

algorithm

time-complexity