string + string 의 시간복잡도는 O(1)?

'+' 연산자를 이용한 문자열 + 문자열을 연산은

막연하게 시간복잡도가 O(1)로 생각하고 있었다.

 

이런 생각을 갖고 문제를 푸는 과정에서 터질게 터지게 되었고

해당 연산을 100만 ~ 1000만번 하면서 시간초과가 발생하게 되었다.

 

string + string 연산은 + 연산자를 통해

뒷 string의 문자를 하나씩 따와서 앞의 string에 연결하는 방식으로 동작하기 때문에
시간 복잡도가 뒷 string의 길이가 된다.

따라서 문제의 상황에서의 시간 복잡도는
O(1)이 아닌 O(뒷 string의 길이)이다.