len()의 시간 복잡도가 O(1)인 이유

len()의 시간 복잡도가 O(1)인 이유가 뭘까?

여기서 잠깐 우리가 배열을 하나 선언했다고 가정하자. 그렇다면 배열의 크기를 알기 위해서는 원소가 얼만큼 저장되었는지 세어봐야 한다. 이러한 방식이라면 len()의 시간 복잡도는 O(n)이 더 타당하지 않을까?

 

이 의문을 해결하면 pop()이 왜 시간 복잡도가 O(1)인지 이해할 수 있다. 파이썬은 어떻게 선언한 배열의 크기를 바로 알 수 있는 걸까?

__len__()

python에서 len()은 실제로는 __len__() method를 호출하는 함수이다. 이 method는 iterable 데이터 구조 클래스에 미리 설계되어있다. 해당 method는 카운터 역활을 한다. 그래서 데이터가 선언되거나 수정(특정 원소 삭제 및 추가 등)될 때 자동적으로 해당 데이터의 크기를 카운터 하여 저장한다. 따라서 이미 저장된 크기를 len()을 호출할 때 반환하므로 시간 복잡도가 O(1)이 되는 것이다.

결론

python에서 len()을 호출할 때마다 배열의 원소 개수를 세는 것이 아닌 미리 원소의 개수를 파악하여 반환한다.

 

참고

https://www.geeksforgeeks.org/internal-working-of-the-len-function-in-python/

Internal Working of the len() Function in Python - GeeksforGeeks