C++中使用find替代内层循环后，时间复杂度是否为O(n²)？

你的两个代码片段时间复杂度并不相同，核心原因在于std::find的底层实现逻辑：

• 第二个代码（内层固定循环）：
  外层循环执行s2.size()次，内层循环固定遍历26次（常数次数），所以整体时间复杂度是O(s2.size())，属于线性复杂度。

• 第一个代码（用std::find替代内层循环）：
  外层循环执行string.size()次，每次调用std::find都会线性遍历整个string（最坏情况下要遍历所有元素），单次std::find的时间复杂度是O(string.size())。因此整体时间复杂度是O(string.size()²)，也就是平方级复杂度。

这里要注意，你代码里每次find的目标是固定值3，完全可以把find操作移到外层循环外面，只执行一次，这样整体复杂度就能降到O(string.size())，和第二个代码的效率一致：

// 优化后的代码：只执行一次find
auto it = find(string.begin(), string.end(), 3);
int index = it - string.begin();
for(int i = 0; i < string.size(); i++) {
    vector[i] = string[index - 1];
}

总结：直接把内层循环换成std::find并不能降低时间复杂度，反而可能因为std::find遍历的范围更大（26次 vs 整个string长度）导致复杂度升高，关键是要避免重复执行不必要的查找操作。

内容的提问来源于stack exchange，提问作者CodingChef