时间戳

首页 > 解决方案 > 金字塔算法的大 O 成本

javascript - 金字塔算法的大 O 成本

问题描述

我正在努力理解大 O 表示法，我想知道：金字塔算法的大 O 成本是多少？

pyramid(2)结果是：

 # 
###

我知道解决它的一种方法是使用嵌套for循环，例如：

function pyramid(n) {
    const totalLengthOfRow = n * 2 - 1
    for (let row = 0; row < n; row++) {
        var line = ''
        var middleCol = Math.floor(totalLengthOfRow / 2)
        
        for (let col = 0; col < totalLengthOfRow; col++) {
            if (col >= middleCol - row && col <= middleCol + row) {
                line += '#'
            } else {
                line += ' '
            }
        }
        console.log(line)
    }
}

那应该是O(n2)对的吧？由于两个for循环都随着增长而n增长。但是如果我使用string.repeat并摆脱内for循环呢？

就像是：

const numberOfHashes = 1 + row * 2
const numberOfSpaces = n * 2 - 1 - numberOfHashes    
var line = ' '.repeat(numberOfSpaces / 2) + '#'.repeat(numberOfHashes) + ' '.repeat(numberOfSpaces / 2)

repeat就像一个for循环，因为它也根据 ? 的大小重复n。

标签： javascriptbig-o

解决方案

假设第二种算法更聪明一些，因为在每一步你都不需要检查（使用条件语句）你必须打印哪个字符。

尽管如此，JSrepeat函数只不过是循环的语法糖。因此，这两种算法（不仅在语义上，而且在渐近上）是等价的，特别是两者都是O(n^2)。

推荐阅读