tsurutanのつぶやき

これが、破壊的イノベーションだっっっ!!

スポンサーリンク

広告

文字列連結 時間計算量を少なくする[Java]

f:id:tsurutan:20150613213051g:plain

文字連結をする際によく書いてしまうコード

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

この時、引数として渡された文字列の長さをaとし個数をnとすると時間計算量は

O(a + 2a + 3a + ..... + na) = O(an2) となってしまい効率が悪い。

しかし、ここでStringBufferを使うことで劇的に改善される。

public String joinWords(String[] words) {
  StringBuffer sentence = new StringBuffer();
  for (String w : words) {
    sentence.append(w);
  }
  return sentence.toString();
}

このようなコードを書けば時間計算量は

O(a + a + a + .... a) = O(an) となりかなり少なくなる。

こういうちょっとしったものが積もりに積もって惨事を招くので気をつけようと思う。

スポンサーリンク

広告