两段C++代码时间复杂度差异及耗时超百倍原因咨询

核心性能差异点拆解 #

1. 致命的全字符串传值拷贝 #

两段代码的strComp函数参数都是string str，这意味着每次调用函数时，都会完整拷贝整个输入字符串。当输入长度达到1e6时，单次拷贝就要处理百万级别的字符，这本身就是巨大的性能开销。而第一段代码还嵌套调用了cutstring，同样是传值拷贝原字符串，等于平白多做了一次百万字符的拷贝操作。

第二段代码虽然也存在传值拷贝的问题，但没有额外的嵌套拷贝，已经比第一段少了一次巨大的开销。（注：如果改成const string& str传引用，还能进一步消除这个拷贝开销）

2. 不必要的子字符串构造与内存操作 #

第一段代码中的cutstring函数需要：

• 初始化空字符串对象，分配初始内存空间
• 循环3次逐个拷贝字符到新字符串，每次+=操作都要检查内存是否足够，必要时触发扩容（即便只拷贝3个字符，内存分配的系统调用开销依然存在）
• 返回新字符串时，可能触发拷贝构造（依赖编译器RVO优化，无法完全消除）

而第二段代码直接访问原字符串的索引位置，没有任何内存分配、拷贝或扩容操作，只是简单的内存读取。

3. 字符串比较的额外开销 #

第一段代码最后需要将构造好的子字符串和"IOI"做全字符串比较，这涉及：

• 先比较两个字符串的长度（虽然这里长度都是3，但依然是额外的检查步骤）
• 逐字符比较直到结束（哪怕第一个字符不匹配，也要走完长度检查的流程）

第二段代码采用短路逻辑判断：只要str[i] != 'I'就立刻返回false，无需继续检查后面的字符，逻辑分支更高效，没有额外的字符串比较框架开销。

4. 函数调用的额外开销 #

第一段代码中strComp需要调用cutstring，涉及函数调用的栈帧创建、参数传递、返回值处理等额外开销。而第二段代码是单函数内的直接逻辑，编译器可以轻松将其内联优化，消除函数调用的开销。

总结 #

第一段代码引入了大量无意义的冗余操作：两次全字符串拷贝、子字符串构造、多函数调用、全字符串比较，这些操作的常数开销在输入长度达到1e6时被无限放大。而第二段代码完全围绕需求做最小化操作，仅做三次内存读取和短路判断，两者的实际执行效率自然会相差百倍以上。

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