python 시간복잡도 질문드립니다.

Question

안녕하세요 알고리즘 기초 공부중인데 갑자기 궁금한게 생겨서 간단한 질문글 올립니다.언어 대부분이 해당되는지는 모르겠지만python에서 len()함수는 매개변수의 문자의 개수를 계산해서 반환하는걸로 알고있습니다.매개변수 n의 문자 개수만큼 작동하므로 O(n)로 표기할 수 있습니다. n의 문자가 10^6개면 10^6번 반복해서 계산하겠죠.단순한 코드면 몰라도 규모가 큰 프로젝트는 최대한 효율적으로 작성할꺼라는 생각에 len() 함수 대신array.index(array[-1])를 생각해봤는데 # array.index(array[-1] &#43; 1)로 수정len(array)와 비교했을때 확장성이 좋은 코드라 할 수 있을까요?봐주셔서 감사합니다 :)

MungGaeDev · Accepted Answer

python에서 len()함수는 매개변수의 문자의 개수를 계산해서 반환엄밀히 따지면 틀린 표현입니다. 추후 다시 공부해 보시길 바라며 array.index(array[-1]) 는 index를 반환하기에 의도대로 작동하더라도 len과 값이 달라지며,시간 복잡도 역시 그대로 입니다, 오히려 비교하는 부분이 더 생겨 더 오래 걸립니다.무엇보다 매개변수의 최종값 array[-1] 과 동일한 값이 중간에 있다면 의도대로 작동하지 않습니다.

판교바닐라라떼 · Answer

Python 내장함수는 대부분 c로 되어있어서 그냥 내장함수 쓰는게 보통은 제일 빠릅니다이미지 같은 Numpy array 데이터라면 numpy 기능으로 길이를 구하는게 더 빠르겠지만, 내장 자료구조의 길이를 구하기 위해 Numpy 기능을 쓴다면 내장 자료구조를 Numpy 배열로 바꾸는 과정에서 시간 및 메모리의 추가 소요가 발생해서 대부분의 경우에 오히려 속도는 더 느려집니다

Clickin · Answer

모든 파이썬 객체는 size 프로퍼티가 있어서 그걸 반환합니다.https://github.com/python/cpython/blob/d6892c2b9263b39ea1c7905667942914b6a24b2c/Include/object.h#L211return var_ob->ob_size;커스텀 class 만들 때 __len__ 잘 정의해주기만 하면 됩니다.

python 시간복잡도 질문드립니다.

3개의 답변

Q&A 목록