21.2 파이썬 기본 연산의 분석

파이썬에서 대부분의 수학 연산은 상수 시간이다. 곱셈은 덧셈이나 뺄셈보다 더 오래 걸리는 편이며, 뺄셈은 훨씬 더 길지만, 실행 시간이 피연산자의 크기에 따라 달라지지는 않는다. 매우 큰 정수는 예외다. 이 경우에 실행 시간은 자릿수에 따라 증가한다.

시퀀스나 사전에서 원소를 읽거나 쓰는 인덱스 연산도 상수 시간이며, 자료 구조의 크기가 영향을 주지 않는다.

시퀀스나 사전을 순회하는 for 루프는 루프 본체의 모든 연산이 상수 시간이라면 일반적으로 선형 시간이다. 예를 들어 리스트의 원소들을 더하는 것은 선형이다.

total = 0

for x in t:

total += x

내장 함수 sum도 같은 일을 하므로 선형이지만, 더 효율적으로 구현되어 있어서 더 빠른 편이다. 알고리즘 분석 관점에서 설명하자면 sum은 최고차항에 더 작은 계수를 갖고 있다.