我在 Big O Runtime 中计数 Math.max 吗？

Question

我无法理解天气或不使用 Math.max 应该算作一个循环，因此应该包含在计算 Big O 运行时中。

我假设 Math.max 找到它必须循环的最大值并比较它提供的所有值。因此它实际上是在循环。

我的 JS 代码：

function getWaterCapacityPerSurface(surface){
    let waterAmount = 0;

    // full loop
    for(let i = 1; i < surface.length - 1; i++){
        const current = surface[i];

        // I assume each slice is counted as a half of the full loop
        const leftSlice = surface.slice(0, (i - 1 < 0 ? 0 : i));
        const rightSlice = surface.slice(i + 1, surface.length);

        // I assume each Math.max is counted as a half of the full loop
        const leftBound = Math.max(...leftSlice);
        const rightBound = Math.max(...rightSlice);

        const canWaterStay = leftBound > current && rightBound > current;
        const currentBound = Math.min(leftBound, rightBound);
        const waterLevel = currentBound - current;

        if(canWaterStay) waterAmount += waterLevel;
    }

    return waterAmount;
}

console.log(getWaterCapacityPerSurface([4,2,1,3,0,1,2]));
// returns 6

Big O 运行时间是 O(N(N+N)) 还是 O(N(N))？

我假设在这种情况下它并不重要，因为我们删除常量，最后它将是 O(N(N+N)) = O(N(2N)) = O(N (N)) = O(N²) 但我只想知道天气我应该把 Math.max/Math.min 算作一个循环以供将来参考。

Answer 1

是的，如果将长度为 n 的参数列表传递给 Math.max()，那么它是一个 O(n) 操作。 Math.max() 遍历每个参数。在 specification.

中查看更多信息

我在 Big O Runtime 中计数 Math.max 吗？

Do I count Math.max in a Big O Runtime?

big-o

runtime