Big-O Notation 也是根据使用的函数计算出来的吗？

Question

我正在学习 Big-O Notation 和算法以提高我的面试技巧，但我不太了解如何获得时间复杂度。

假设我想对以下列表的所有元素求和。

std::vector<int> myList = {1,2,3,4,5} ;

案例 1：

int sum = 0;
for (int it: myList)
{
  sum += it;
}

案例二：

int sum = std::accumulate(std::begin(myList), std::end(myList), 0);

情况 1 是 O(N)，情况 2 显然是 O(1)，但我确定这些函数会进行某种迭代，所以问题是 Big-O 符号是否仅从该块或所用函数的书面代码。

Answer 1

我想这个例子应该会给你一个想法。

int sum(std::vector<int> const& list)
{
   int result = 0;
   for( elem const& : list )
   { 
       result += elem;
   }
   return result;
}

int main()
{
   std::vector<int> test = {1,2,3,4,5,6};
    

   // O(n)
   int sum1 = 0;
   for( elem const& : test )
   {
      sum1 += elem;
   }

  // O(???)
  int sum2 = sum(test);
}

Answer 2

如果你谈论big-O，你必须谈论一些正在处理的数据单元。您的案例 1 和案例 2 都是 O(N)，其中 N 是容器中的项目数：单位是 int.

您倾向于希望单位和 N 是您程序中最有可能 grow/vary 的事物的计数。例如，如果你在谈论处理电话簿中的名字，那么名字的数量应该是 N；即使个别名称的长度也有些变化，但随着您的程序处理更大的电话簿，平均名称长度不会增加。

类似地，如果您的程序必须处理任意数量的容器，这些容器的长度往往大致相同，那么您的单元可能是一个容器，然后您可以考虑您的代码 - 案例 1 和案例 2 -关于容器数量的 big-O O(1)，因为无论程序中某人周围有 0、1、10 还是一百万个其他容器，您只处理一个 - myList。但是，任何单个 accumulate 调用对于任何单个容器的 int 都是 O(N)。

Answer 3

case 2 is apparently O(1)

谁说的？ cplusplus.com 说 accumulate:

Complexity
Linear in the distance between first and last.

这与您的案例 1 代码的复杂度相同。

（我也检查了 cppreference.com 但在这种情况下它没有说明复杂性。）

Answer 4

对于时间复杂度的评估，计算花费常数时间的操作更有意义。因此 sum 不是特别好的候选人，除非

总是对相同数量的元素求和，或者
总长度的分布是已知的，并且与进行调用的环境无关（以避免任何偏差）。

这样的评价很不一般。

Big-O Notation 也是根据使用的函数计算出来的吗？

Is Big-O Notation also calculated from the functions used?

c++

algorithm

time

big-o