c++ - 从头到尾再返回 vector 的复杂性

Question

我正在尝试熟悉算法的复杂性评估。总的来说，我认为这是一种很好/优雅的做法，但在具体情况下，我需要它来表达我的 C++ 代码的时间复杂度。

我有个小疑问。假设我有一个算法，它只从 std::vector 的开头读取数据，直到结尾；然后它从头到尾执行相同的操作(索引“从 0 到 N”然后是“从 N 到 0”的 2 个循环也是如此)。

• 我对自己说，这东西的复杂度是 O(2N):这是正确的吗？
• 一旦到达开头，假设我想重新开始读取从头到尾的所有数据(总共传递 vector 的 3 倍):复杂度为 O(3N) 吗？

这可能是一个愚蠢的疑问，但我还是希望有人对我的思考过程发表意见。

Answer 1

Big-O 表示法简单地表示:

f(n) = O( g(n) ) if and only if f(n) / g(n) does not grow to infinity as n increases

您需要做的是计算您正在执行的操作数，即 f(n)，然后找到一个函数 g(n)增加至少与 f 一样快。

在你的一个方向然后返回的例子中，操作的数量是f(n) = 2n因为每个元素被读取两次，所以，你可以选择g(n ) = n。因为 f(n)/g(n) = 2n/n = 2 显然不会增长到无穷大(它是一个常数)，你有一个 O(n) 算法.

当然，它也是一个 O(2n) 算法:因为当您将 g(n) 乘以一个常数时，“增长到无穷大”属性不会改变, 任何 O( g(n) ) 也根据定义是一个 O( C g(n) ) 算法用于任何常量 C。

它也是一个 O(n²) 算法，因为 2n/n² = 2/n 向零递减。大 O 符号仅提供复杂性的上限。