algorithm - 这个函数的时间复杂度是多少？

Question

这应该很简单，但我在尝试查找我的 printRow() 函数的时间复杂度时遇到了问题。

我的猜测是，由于 printChar() 是 O(n)，printRow() 必须是 O(a + b)。

我不确定这是正确的还是不正确的。任何解释的帮助都会很棒!

// prints a row consisting of " " a times and "*" b times...
// a and can be <, =, or > b
// complexity: O(?)
function printRow(a, b) {
     var str = '';
     // prints " " a times
     str += printChar(" ", a);
     // prints "*" b times
     str += printChar("*", b);
     return str;
}

// prints char n times
// complexity: O(n) because of the for loop
function printChar(char, n) {
    var str = '';
    for (var i=0; i<n; i++) {
        str += char;
    }
    return str;
}

Answer 1

其中很大一部分是 += 的实现。

在最坏的情况下，为了生成更长的字符串，必须为结果字符串分配足够大的内存。接下来是将字符串的全部内容复制到新位置。

像这样复制整个字符串是一个 O(n) 操作。在添加每个字符的同时执行此操作，一次添加一个字符会使整个算法复杂度为 O(n^2)。

最佳情况:您预先分配所需的总空间，然后用您需要的数据填充它。这是 O(n)。

在两者之间有一个常见的 O(n) 策略，其中分配给字符串的空间可能大于它需要的空间，并且随着它的增长，它会填满它。当需要按当前大小分配更多空间时(比如将大小加倍)，将当前字符串复制到那里，然后该过程可以继续。

每次扩展都和以前一样昂贵，但它们的频率也大大降低，并且确实提供了分摊的 O(n) 运行时间。