如何计算包含内部辅助函数的函数的时间复杂度？

计算包含内部辅助函数、多种循环结构的代码复杂度，遵循两个通用逻辑：

• 先把代码拆分为多个按顺序执行的独立阶段，分别计算每个阶段的复杂度，最终整体复杂度取所有阶段中的最高量级
• 遇到内部函数调用时，先单独算出该内部函数的单次调用时间复杂度，再乘上外部的调用次数，就能得到这部分的总复杂度

我们先设输入数组nums的长度为n，按上述规则拆分计算：

阶段1：while循环生成container数组 #

这段while循环的逻辑是枚举所有满足下标条件zero < one < two的三元组，将对应元素的和存入container。所有符合条件的三元组总数为组合数C(n,3) = n*(n-1)(n-2)/6，属于O(n³)*量级，因此本阶段时间复杂度为O(n³)，最终container的长度也为O(n³)。

阶段2：遍历container调用isPrime统计素数数量 #

首先计算内部函数isPrime的单次调用复杂度：你当前的实现是从2遍历到待判断数的前一位，最坏情况下（待判断数是素数）需要遍历k-2次（k为待判断的数值），因此单次调用时间复杂度为O(k)，k为传入的参数大小。
接下来结合调用次数计算本阶段总复杂度，分两种常见场景：

• 如果题目限定nums中的元素为固定范围的整数（比如常见的元素<=1000的场景），那么三个元素的和最大为常数，isPrime的单次复杂度为O(1)，本阶段总复杂度为 O(n³) * O(1) = O(n³)
• 如果nums的元素大小和数组长度n正相关（比如元素最大为n），那么三个元素的和最大为3n，isPrime的单次复杂度为O(n)，本阶段总复杂度为 O(n³) * O(n) = O(n⁴)

小提示：如果把isPrime优化为只遍历到待判断数的平方根，单次调用的复杂度会降到O(√k)，对应上述两种场景的第二阶段复杂度会分别变为O(n³) 和 O(n³ * √n) = O(n^3.5)

你之前猜测的O(n log n)是不正确的，该函数的最坏时间复杂度至少为O(n³)，具体上限由nums数组的元素大小范围决定。

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