简单字符串连接的时间复杂度

本文介绍了简单字符串连接的时间复杂度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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