内层循环次数由数组元素值决定的嵌套for循环时间复杂度是多少

给定代码如下：

for (int i = 0; i < nums.size(); i++) {
    for (int j = 0; j < nums[i]; j++) {
        // ...
    }
}

这段代码的总执行次数等于数组所有元素的数值之和，整体时间复杂度没有固定结论，需要结合数组元素的取值规则判断：

• 如果数组元素的取值上限是和数组长度n无关的固定常数，比如所有元素都不超过100，那么总执行次数最多为100*n，时间复杂度为O(n)，题目给出的示例数组元素都属于小常数范围，符合这个场景
• 如果数组元素的取值和数组长度n正相关，比如元素最大值为n，总执行次数最高可达n²量级，时间复杂度为O(n²)
• 如果数组元素取值是比n更高阶的量级（比如指数级），时间复杂度也会对应升高，比如元素最大值为2ⁿ时，时间复杂度为O(n·2ⁿ)

注意：如果题目没有额外说明数组元素和数组长度的关联规则，默认认为元素取值是独立于n的固定常数范围，这种情况下的通用结论为O(n)。

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