Big-O 表示法是否也是根据所使用的函数计算的？

Question

我正在学习 Big-O 表示法和算法来提高我的面试技巧，但我不太明白如何获得时间复杂度。

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

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

情况1：

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

案例2：

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

情况 1 是 O(N)，情况 2 显然是 O(1)，但我确信这些函数会进行某种迭代，所以问题是 Big-O 表示法是否仅根据该书面代码计算块或所使用的功能。

Answer 1

如果您谈论 big-O，则必须谈论正在处理的某些数据单元。您的情况 1 和情况 2 都是 O(N)，其中 N 是容器中的项目数：单位是 an int。

您倾向于希望单位（N 是其计数）是您的程序中可能增长/变化最大的事物。例如，如果您正在谈论处理电话簿中的姓名，那么姓名的数量应该是N；尽管个人姓名的长度也有些变化，但当您的程序处理更大的电话簿时，平均姓名长度不会增加。

类似地，如果您的程序必须处理任意数量且长度大致相同的容器，那么您的单元可能是一个容器，然后您可以将您的代码（情况 1 和情况 2）视为 big-O就容器数量而言，O(1)，因为无论程序中某个人周围有 0、1、10 还是一百万个其他容器，您只处理一个 - myList。但是，accumulate对于任何单个容器的 s 来说，任何单个调用都是 O(N) 的int。