javascript - 如何计算包含可能在任何点终止的内部循环的代码片段的时间复杂度

Question

如何计算下面代码片段的时间复杂度？

let count, barHeight, result = 1 << 31;
for(let i = 0; i < heights.length; i++) {
    count = 1;
    barHeight = heights[i];
    for(let j = i - 1; j >= 0; j--) {
        if (heights[j] >= barHeight) {
            count++;
        } else {
            break;
        }
    }

    for(let k = i+1; k< heights.length; k++) {
        if (heights[k] >= barHeight) {
            count++;
        } else {
            break;
        }
    }

    result = Math.max(result, count*barHeight);
}

基本上这个片段是计算任何索引i，计算heights数组中有多少个相邻索引不小于heights[i].

我有点困惑如何计算这种情况下的时间复杂度。 2 个内部循环可能会在任何点停止。

谢谢

Answer 1

它是二次O(n^2)。

在评估时间复杂度时，您应该始终考虑最坏的情况，除非存在客观的摊销，证明最坏的情况可以由所有其他情况摊销。

该算法是二次的。