목록시간복잡도 (1)
Kelly's journey to a coding master
[python] len()은 어떻게 O(1)으로 동작할까?
C언어에서는 직접 구현해야 하는 기능들을 파이썬에서는 내장함수을 통해 쉽게 접근이 가능하다. 그런데 파이썬의 편리한 함수들을 사용하다보면 시간복잡도에 대한 우려를 하게 된다. 파이썬이 워낙 사용자에게 친화적인 언어이다보니 나도 모르게 컴퓨터에게는 과중한 일을 시키고 있을지도 모르니 말이다. C언어에서 배운 구현 방식을 통해 파이썬에서 사용하는 함수들의 시간복잡도를 예상하곤 하는데, 그러던 중 파이썬에서 자주 사용되는 len() 함수의 시간복잡도에 대해 궁금증이 생겼다. 분명 C언어에서 리스트의 길이를 구할 때는 리스트를 traverse하면서 길이를 구하게 되는데, 이 경우 시간복잡도가 해당 함수를 불러올 때마다 O(N)이 될 것이고 이렇게 되면 함수를 매번 호출하기가 부담스러워질 수 밖에 없다. 여러 파..
사소한 궁금증
2022. 7. 8. 14:41