for循环内调用max()函数的最坏时间复杂度是多少？

结论 #

你推导的总时间复杂度为*O(N²)*是正确的，GeeksforGeeks上的对应标注存在错误。

具体原因 #

• 首先明确：代码中调用的max(nums)是接收整个数组作为参数的求最大值函数，这类实现需要遍历数组内所有元素才能得到结果，时间复杂度确实为O(N)，其中N为nums的元素个数。
• 外层for循环的执行次数恰好等于nums.size()也就是N次，每次循环内的核心耗时操作就是这个*O(N)的max调用，cout操作是固定耗时的O(1)*操作可以忽略。
• 按照嵌套复杂度的计算规则，外层循环N次，每次循环耗时O(N)，总复杂度就是N * O(N) = O(N²)。
• 之所以GeeksforGeeks会出现错误标注，大概率是标注者混淆了max的实现版本：如果是接收两个参数比较大小的max函数，时间复杂度是O(1)，这种情况下总复杂度才是O(N)，但和你给出的代码场景完全不符。

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