파이썬 find 함수와 시간복잡도

*18년도 카카오 기출 [방금 그 곡] 문제 풀이 도중

n^2(문자열 간의 관계이니 정확히는 len_str1*len_str2)연산이라고 생각해서 KMP를 구현하려고 했다.

그 전에 확인 차 n^2으로 생각하는 그냥 find를 사용하는 방법을 해서 풀었는데,
시간 초과 없이 잘 풀리는것을 확인.

내장 함수 시간 복잡도를 검색해도 잘 나오지 않아 직접 실험하기로...

일반적인 연산 4천만 기준 몇초인지 확인 : 3초

print("==========================")

temp = datetime.datetime.now()
dateformat = "%s"
curr = temp.strftime(dateformat)
i = 0
while(i < 40000000):
    i+=1  ##4천만 3초
temp2 = datetime.datetime.now()
after = temp2.strftime(dateformat)

print(int(after) - int(curr))

---

str2에 2글자씩 넣을 것이기에 반복문 2천만

import datetime


str1 = "abc"
str2 = ""
for i in range(20000000):
    str2+="ab"
str2+="c"

print("==========================")

temp = datetime.datetime.now()
dateformat = "%s"
curr = temp.strftime(dateformat)
# i = 0
# while(i < 40000000):
#     i+=1  ##4천만 3초
ind = str2.find(str1)
temp2 = datetime.datetime.now()
after = temp2.strftime(dateformat)

print(int(after) - int(curr))

print(str2[ind:])
print("index: ",ind)

print("================after find===================")

leng = len(str2)
temp = datetime.datetime.now()
curr = temp.strftime(dateformat)

for i in range(leng):
    if str1 == str2[i:i+3]:
        print("found ind:",i)
        break

temp2 = datetime.datetime.now()
after = temp2.strftime(dateformat)

print(int(after) - int(curr))

결과 :
find함수 : 0~1초
단순 반복문 : 8초 (3*4천만이니 대략 예상한 결과이다.)

결론 : O(len_str1*len_str2)이 아닌, O(len_str1+len_str2) 연산으로 되어있음