如何计算包含内部循环的代码段的时间复杂度，这些代码片段可能随时终止

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数组的相邻索引有多少不小于highlight[i]。

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

谢谢

Answer 1

它是二次 O（n^2）。

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

这个算法是二次的。