简单字符串连接的时间复杂度 [英] Time complexity of simple string concatenation

问题描述

以下方法的费用是多少.您如何计算?

What is the cost of the following method. How do you calculate it?

public String joinWords(String[] words) {
    String sentence = "";
    for (String w : words) {
        sentence = sentence + word;
    }
    return sentence;
}

推荐答案

假定两个长度为r和s的字符串的字符串连接成本为O(r + s)-历史上在Java中就是这种情况但可能会更改-运行时间为O(mn)，其中n是字符总数在输入字符串中，m是输入字符串的数量.

Assuming that the cost of string concatenation is O(r + s) for two strings of lengths r and s - which historically was the case in Java but may change going forward - the runtime would be O(mn), where n is the total number of characters in the input strings and m is the number of input strings.

要看到这一点，请注意，如果字符串长度为n1，n2，...，n_m，则运行时将为

To see this, note that if the string lengths are n1, n2, ..., n_m, then the runtime will be

n1 +(n1 + n2)+(n1 + n2 + n3)+ ... +(n1 + n2 + ... + n_m)

n1 + (n1 + n2) + (n1 + n2 + n3) + ... + (n1 + n2 + ... + n_m)

= m(n_1)+(m-1)(n_2)+(m -2)(n-3)+ ... + n_m

= m(n_1) + (m - 1)(n_2) + (m - 2)(n-3) + ... + n_m

= m(n_1 + n_2 + ... + n_m)-n_2-2n_3-3n_4-...-(m-1)n_m

= m(n_1 + n_2 + ... + n_m) - n_2 - 2n_3 - 3n_4 - ... - (m - 1)n_m

受n_1 + ... + n_m = n的约束，当n_1 = n且所有其他值均为0时，此值最大化.在这种情况下，运行时间变为mn，因此运行时间为O(mn)

Subject to the constraint that n_1 + ... + n_m = n, this is maximized when n_1 = n and all the other values are 0. In that case, the runtime becomes mn, so the runtime is O(mn).

这篇关于简单字符串连接的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！