计算 Big-O 运行时

Question

我急需一些关于为以下 C++ 函数计算 Big-O 运行时的指导：

Fraction Polynomial::solve(const Fraction& x) const{
    Fraction rc;
    auto it=poly_.begin();
    while(it!=poly_.end()){
        Term t=*it;
        //find x^exp
        Fraction curr(1,1);
        for(int i=0;i<t.exponent_;i++){
            curr=curr*x;
        }
        rc+=t.coefficient_*curr;
        it++;
    }
    return rc;
}

这对我来说仍然是一个新概念，所以我在正确理解它时遇到了一些麻烦。我假设至少有两个操作发生一次（auto it = poly_.begin，最后是 return rc），但我不确定如何计算操作次数while 循环。根据我的教授的说法，正确的运行时间不是 O(n)。如果有人可以提供任何指导，将不胜感激。我想了解如何回答这个问题，但我在网上找不到其他类似此功能的东西，所以我来了。谢谢。

Answer 1

假设这是一个 n 阶多项式（最高项的 n 次方）。

在外部 while 循环中，您将迭代 n+1 项（两边都包含 0 到 n）。

对于每一项，在内部 for 循环中，您将执行乘法 m 次，其中 m 是当前项的幂。由于这是一个 n 阶多项式，m 的范围从 0 到 n。平均而言，您将执行乘法 n/2 次。

整体复杂度为 O((n+1) * (n/2)) = O(n^2)

Answer 2

我假设您想在给定点（有理数，因为它是作为分数给出的）计算某个多项式（假设为 A_n*X^n + ... + A_0）。

第一个 while 循环将遍历多项式的所有单独分量。对于 n 次多项式，这将产生 n + 1 次迭代，因此仅外层循环就需要 O(n) 时间。但是，对于多项式的每一项（让我们说秩 i），您必须计算 X^i 的值，这就是您的内部 for 循环所做的。它使用线性方法计算 X^i，产生线性复杂度：O(i).

由于您有两个嵌套循环，因此总体复杂度是通过乘以循环的最坏情况时间复杂度得到的。由此产生的复杂度由 O(n) * O(n) = O(n^2) 给出。（第一项表示while循环的复杂度，而第二项表示计算X^i的最坏情况时间复杂度，当i == n时为O(n)）。

计算 Big-O 运行时

Calculating Big-O Runtime

c++

big-o

code-analysis

time-complexity