c++ - 考虑STL容器操作的复杂性

Question

在计算算法的复杂性时，我们是否考虑了 STL 容器操作的时间/空间复杂性？例如，给定以下代码片段:

// str is an std::string, and size = str.size()
std::string res;
for (int i = 0; i < size; i++)  // size is some integer
    res += str[i];  

就是上面代码片段的时间复杂度: O(size) 因为循环？

或

O(size^2):因为在每个循环迭代中我们都附加到一个 std::string 并且这是一个线性时间复杂度操作？

如果没有通用答案，我想问的是我们在面试时需要考虑什么。是否有一种事实上的约定来考虑/忽略 STL 容器操作的时间/空间复杂性？

谢谢。

编辑:

即使示例代码没有显示完整的图片，我的问题是在计算算法的复杂性时是否需要考虑 STL 容器操作的复杂性。

Answer 1

当然，您需要考虑各个操作的复杂性，无论它发生在您的代码中还是在库函数中。事实上，标准 C++ 库指定了容器操作的时间复杂度，以及算法的时间复杂度，以使您的计算成为可能。

在您的特定示例中，答案取决于字符串数组 str[] 中各个 str 元素的大小。如果每个元素字符串的长度大致为size，那么答案就是O(size²)。如果每个元素都有固定大小，那么答案就是 O(size)，因为常数长度可以从表达式中分解出来。