c++ - 为什么不将比较因素纳入 Big O 计算？

Question

当你有代码时:

for(int i = 0; i<N; i++)
{
   array[i] += N
}

不就是每次循环迭代的时候都会比较变量i和N吗。就此而言，它不是每次循环迭代时都会向 i 加 1 吗？

那么，这不是每次循环迭代 3 次操作吗？

为什么我们通常忽略这些操作并说这段代码是 O(n)？它与这些操作如何使用 CPU 有关系吗？

Answer 1

大 O 表示法不处理操作的实际成本，而是处理该成本如何随着问题的大小而增长。就此而言，O(n)并不意味着成本是n ，但成本随着问题的规模线性增长。无论 100 个元素的成本是多少，200 个元素都会翻倍，1000 个元素会翻倍。同理 O(n^2)意味着成本以二次方增长，因此如果问题的规模翻倍，操作成本将翻两番，如果规模增加十倍，则成本增长一百倍。

常量在这里并不重要，它们通常被分解。此外，在许多分析中，成本甚至不是实际时间或内存成本，而是其他操作的成本。例如，std::map::find据说函数有O( log N ) , 无论 key 类型如何。原因完全一样:O( log N )意味着无论用 N 在 map 中查找成本如何elements 是，它将以对数方式增长。

举一个有启发性的例子，考虑一个相当荒谬的问题:从完整的书籍内容中找到一本书的作者，以及两个实现。在第一个实现中，您使用 std::map<std::string, std::string>第一个std::string在哪里是书的内容，第二是作者的名字。第二种实现将书的内容散列为一个整数，并将其存储到一个无序的 std::vector< std::pair<int, std::string> > 中。 , int作为哈希和 std::string是作者的名字(假设没有散列冲突)。在 map 中找到这本书的作者的成本是O( log N )在 vector 中找到作者的成本是 O( N ) ，这更糟。但是，这些成本隐藏了比较的复杂性，与比较散列的成本相比，比较 map 中整本书内容的成本可能巨大，直至单次比较一本书的内容可能比 vector 案例中所需的所有比较更昂贵。

Big-O 符号仅处理成本如何随着问题的大小而增长，并隐藏了每个操作的实际成本。在分析算法的复杂性时，个别成本被忽略，但您仍应注意它们，因为大 O 表示法并不能说明全部情况以及运行算法的实际成本将产生您在分析中忽略的那些恒定成本。