파이썬 기본 연산 분석

파이썬 기본 연산 분석¶

대부분의 산술 연산은 상수 시간이다. 곱셈은 덧셈이나 뺄셈보다 대개 오래 걸리고, 나눗셈은 더 오래 걸리지만, 이들의 실행시간은 피연산자의 크기와는 상관이 없다. 매우 큰 정수들은 예외이긴 하다. 그런 경우, 실행시간은 자릿수에 따라 증가한다.

인덱스 연산(시퀀스나 사전에 들어있는 원소들을 읽거나 쓰는 것) 또한 데이터 구조의 크기에 상관없이 상수 시간이다.

시퀀스나 사전을 쭉 거치는 for 루프는 본문에 있는 연산들이 모두 상수 시간인 한, 일반적으로 선형이라고 보면 된다.

total = 0

for x in t:

total += x

내장 함수인 sum 또한 선형으로, 위와 동일한 작업을 하지만 더 효율적으로 구현되었기 때문에 약간 빠를 뿐이다. 알고리즘 분석의 관점으로 표현한다면 최고차항의 계수가 더 작은 것이다.

하지만 여러분이 문자열리스트를 '더하는 데' 동일한 루프를 쓴다면, 문자열 연쇄가 선형이기 때문에 실행시간은 이차가 된다. 그래서 문자열 메소드인 join이 보통은 더 빠른데, 이 경우 문자열의 총 길이에 대해 선형인 이유 때문이다.

경험적으로 생각한다면 루프의 본문이 O(n^a)이면, 루프 전체는 O(n^a+1)인 것이다. 하지만 여러분이 일정 숫자만큼 루프가 돌고 종료된다는 사실을 보일 수 잇는 경우엔 예외다. 만약 어떤 루프가 n에 상관없이 k번 실행된다면, 그 루프는 k가 큰 수라고 하더라도 O(n^a)라고 봐도 무방하다.

k를 곱한다고 해서 증가 기준이 바뀌지는 않으며, 나눗셈도 마찬가지다. 그래서 만약 어떤 루프의 본문이 O(n^a)이고 n/k번 실행된다면, 그 루프는 k가 큰 수라고 하더라도 O(n^a+1)이다.

상수 시간인 인덱싱과 len을 제외한 대부분의 문자열과 튜플 연산은 성형이다. 내장 함수인 min과 max도 선형이다. 슬라이스 연산의 실행시간은 출력의 길이에 비례하지만, 입력의 크기에는 독립적이다. 모든 문자열 메소드 또한 선형이지만, 문자열의 길이가 어떤 상수로 제역되어 있다면(예를 들어, 하나의 문자에 대한 연산이라든지) 상수 시간으로 취급된다.

리스트 메소드 대부분은 선형이지만, 몇몇 예외가 있다.

• 리스트의 끝에 원소를 더하는 것은 평균적으로는 상수 시간이다. 가끔 자리가 모자라면, 더 넓은 위치로 복사되긴 하지만 n번의 연산에 대한 전체 시간은 O(n)이기 때문에 하나의 연산에 대한 '할부 시간'은 O(1)이라고 말한다.
• 리스트의 끝에서 원소를 제거하는 것은 상수 시간이다.
• 정렬은 O(n log n)이다.

사전 연산과 메소드 대부분은 상수시간이지만, 마찬가지로 몇 가지 예외가 있다.

• copy의 실행시간은 원소의 개수에 비례하나, 원소의 크기에는 비례하지 않는다(원소 자체가 아니라 레퍼런스만을 복사)
• update의 실행시간은 매개변수로 전달된 사전의 크기에 비례하며, 업데이트 되는 대상인 사전의 크기에는 비례하지 않는다.
• keys, values 그리고 items는 새로운 리스트를 반환하기 때문에 선형이다. iterkeys, itervalues, iteritems는 반복자를 반환하기 때문에 상수 시간이다. 하지만 반복자를 루프로 도는 경우 루프 자체는 선형이다. 'iter' 함수들을 쓰면 시간을 약간 줄여주지만, 여러분이 접근하고자 하는 원소의 개수를 고정시키지 않는 이상은 증가 기준을 변화시키지는 못한다.

사전의 성능은 컴퓨터 과학이 일으킨 작은 기적들 중 하나다.

이미지 출처: https://m.blog.naver.com/PostView.nhn?blogId=heungmusoft&logNo=220725115246&proxyReferer=https%3A%2F%2Fwww.google.com%2F

내용 출처: 복잡계와 데이터 과학