index(),find(),count()와 시간복잡도

전에는 의식하지 않다가 백준에서 계속 시간초과가 떠서 확인해보고 싶었다.

 

알고리즘 문제를 풀다보면 문자열,리스트 안에 값을 찾기 위해 index,find,count와 같은 함수를 쓸때가 있다.

 

그냥 O(1)처럼 파이썬에서 뙇! 찾아주는 줄 알았다. 그러나 아니다.

 

위와 같은 함수들은 그저 for문을 함수로 간략화 시킨것일뿐, 결국은 for문을 돈다!

 

내가 인덱싱을 한것도 아니고 파이썬한테 찾아줘~하고 무책임하게 던져줬으니, 파이썬은 그냥 모든 값을 찾다가 나오면 반환해주는 형식이었다.

 

만약 함수문(for 문) 안에서 이러한 함수들을 쓰면 시간 복잡도가

 

O(N^2)가 된다.