求解给定C++代码的时间复杂度，附推导步骤，验证我推导的O(n²)是否正确

逐模块复杂度拆解 #

• 基础框架开销
  • 单次读取测试用例数T的操作是O(1)，可忽略
  • while (T--) 是外层循环结构，本身的轮次逻辑不产生额外线性开销，真正的成本来自每轮循环内部的处理逻辑
• 单测试用例的输入环节
  • 读取数组长度n、拷贝n到nClone、申请长度为n的动态数组p都是O(1)操作
  • 遍历数组p读入n个元素的for循环，实际执行n次读操作，复杂度确实为O(n)，和你最初的标注一致
• 核心while (n != 0)循环模块
  这部分需要把每轮循环内的操作拆解开算，不能直接标注O(n²)就跳过推导：
  1. *max_element(p, p + n)：标准库实现是遍历当前长度为n的数组找最大值，单次时间复杂度O(n)
  2. find(p, p + n, 找到的最大值)：在当前长度为n的数组中定位最大值的下标，标准库实现是线性遍历，单次时间复杂度O(n)
  3. 把从最大值下标位置到数组末尾的元素追加到pDash：这部分执行次数等于「当前数组长度 - 最大值下标」
  4. 更新n为最大值下标，本身是O(1)操作
     最坏场景下（数组最大值每次都落在数组头部，每轮处理后数组长度只比上一轮少1个元素），循环内部所有max_element、find操作的总执行次数为：2*(n + (n-1) + (n-2) + ... + 1) = n(n+1)，属于O(n²)量级。另外vector的push_back是均摊O(1)操作，所有元素一共只会被追加1次，总开销O(n)，属于被高阶项覆盖的低阶成本。这部分你最初标注的O(n²)量级是正确的，只是没把里面的标准库操作开销拆细。
• 输出环节
  • 遍历pDash打印nClone个元素的for循环，执行n次打印操作，复杂度O(n)，和你的标注一致
  • delete[] p是O(1)操作

对你原有推导的校验 #

你最初的累加计算式是O(T + n + n² + n) = O(T + 2n + n²) = O(n²)，整体最高阶的结论方向是对的，但推导过程存在两处容易混淆的疏漏：

1. 混淆了嵌套循环和顺序执行的复杂度计算规则
   你把外层while(T--)的T次开销，当成和内部n相关操作顺序执行的线性项直接累加，但实际上T对应的循环是外层框架，每跑一次T的循环，内部就要执行一整套O(n²)的处理流程。如果是多测试用例场景，总复杂度应该是O(所有测试用例的(n_i² + n_i))之和，当单测试用例规模统一为n时，总复杂度为O(T*n²)，而不是把T和n²当成顺序执行的两个模块写成O(T + n²)。如果是单测试用例场景（T=1），那你的计算完全没问题。
2. 漏掉了核心循环里两次线性遍历的开销，但这部分开销本身是n²量级，不会改变最终的高阶复杂度结论，只是推导逻辑不够完整。
3. 没算vector追加元素的均摊开销，但这部分总开销是O(n)，属于低阶项，不会影响渐近复杂度的结果。

最终结论 #

• 如果是单测试用例（T=1）的场景，你推导的O(n²)结果完全正确，所有低阶的线性项都可以在渐近分析中被忽略
• 如果是多测试用例的场景，正确的严格复杂度是O(T*n²)，你之前把T当线性项累加的写法，是把嵌套循环的结构误判成了顺序执行的独立模块，不过只要场景是单测试用例，最终O(n²)的结论是站得住脚的。

补充说明：渐近复杂度分析的核心是抓最高阶项，只要没有把乘算的嵌套关系错加成线性关系，低阶项的疏漏一般不会改变最终的量级判断。

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