以下方法的成本是多少？你是怎么计算的？
public String joinWords(String[] words) { String sentence = ""; for (String w : words) { sentence = sentence + word; } return sentence; }
c0vxltue1#
假设两个长度为r和s的字符串串联的成本是O（r + s）-这在Java but may change going forward中是历史上的情况-运行时将是O（mn），其中n是输入字符串中的字符总数，m是输入字符串的数量。要看到这一点，请注意，如果字符串长度为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 + 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）。
1条答案
按热度按时间c0vxltue1#
假设两个长度为r和s的字符串串联的成本是O（r + s）-这在Java but may change going forward中是历史上的情况-运行时将是O（mn），其中n是输入字符串中的字符总数，m是输入字符串的数量。
要看到这一点，请注意，如果字符串长度为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 + 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）。