Python String concat 시간복잡도

면접 중 코드 리뷰 시간에 내가 string += string의 형태로 쓴 것을 시간복잡도 계산에 넣지 않자 면접관님이 이 부분을 가리키시며 이것까지 포함하면 시간복잡도가 얼마가 나오겠냐고 물어보신 적이 있었다. 전혀모르겠지만 3년동안 모아온 내 경험적 빅데이터 feeling으로 이 스트링 길이만큼 더 걸리겠구나 해서 O(N) -> O(N^2)으로 답변을 바꿨는데 이제보니 잘 찍어서 맞게 대답하긴 했다(?)

그래서 직접 계산하게 된 string + string 겸 문자열 뒤집기의 시간복잡도

code

import timeit

st = "abcde"*300000
ret1, ret2,ret3,ret4, ret5 = "","", "", "", ""


# for문으로 더하기
start1 = timeit.default_timer()
for i in range(len(st)-1, -1, -1):
    ret1 += st[i]
#print("ret1:",ret1)
stop1 = timeit.default_timer()
print(stop1 - start1)

# join with reverse
start2 = timeit.default_timer()
ar = list(st)
ar.reverse()
ret2="".join(ar)
#print("ret2:",ret2)
stop2 = timeit.default_timer()
print(stop2 - start2)

# join with reversed
start3 = timeit.default_timer()
ar2 = reversed(list(st))
ret3="".join(ar2)
#print("ret3:",ret3)
stop3 = timeit.default_timer()
print(stop3 - start3)

# reversed(s)
start4 = timeit.default_timer()
ret4 = "".join(reversed(st))
#print("ret4:",ret4)
stop4 = timeit.default_timer()
print(stop4 - start4)


# s[::-1]
start5 = timeit.default_timer()
ret5 = st[::-1]
#print("ret5:",ret5)
stop5 = timeit.default_timer()
print(stop5 - start5)

result: 3000000

26.6578629
0.45415009999999967
0.5463644000000016
0.4610163000000007
0.04074839999999824

result: 5000000

74.115471
0.7088369000000085
1.0676136000000014
0.8729143999999991
0.08702959999999393

1번 for문으로 하나씩 더하기의 시간복잡도는 O(N^2) 이다. 파이썬에서 string A + string B를 하면 O(len(A))+O(len(B))로 완전히 새로운 스트링을 만든다고 한다. 자바에서의 literal String처럼 새로운 메모리에 복사해야 하니 그렇다고 한다. 압도적으로 느리다

2번은 일단 list로 만드는데에 O(N), reverse 하는데에 O(N)이다.
reverse가 왜 O(N)일까 봤더니 내부적으로

    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }

이런식으로 앞뒤를 스왑하는 식으로 구현되어 있었다. n/2만큼 대충 5번의 연산을 하니까 O(N)이다. 그리고 .join()면 딱 O(output)만큼 이라니까
대충 O(5N)정도는 되겠지만 O(N)으로 훨씬 빠르다.

5번의 경우 뒤에서부터 접근해 처음까지 쭉 보니까 찐 O(N)으로 예상된다. 이게 제일 빠르다

3, 4번은 2번이랑 비슷한데 조금씩 차이가 있다. 특히 3번이 다른것보다 느린게 의문인데 reversed()와 reverse()의 차이를 알아봐야겠다