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

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).

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

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

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

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

what is the time complexity for this function?

algorithm

big-o