[이것이 코딩 테스트다] 2강 - 알고리즘 성능평가

📍 복잡도

• 시간복잡도: 알고리즘의 수행시간에 따른 복잡도
• 공간복잡도: 알고리즘의 메모리 사용량에 따른 복잡도

→ 복잡도가 낮을수록 좋은 코드

📍 복잡도 표기 방법

• 빅오표기법(Big-O)

  → 함수의 상한만 남김

  ex) 연산횟수가 3N**2+5N+1,000,000인 알고리즘 ⇒ O(N**2)

📍 복잡도 순서

아래로 갈수록 복잡도 높음

1. O(1): 상수 시간

2. O(logN): 로그 시간

3. O(N): 선형 시간

4. O(NlogN): 로그선형 시간

5. O(N**2): 이차 시간

6. O(N***3): 삼차 시간

7. O(2**N): 지수 시간

ex.

array = [3, 5, 1, 2, 4]  # 데이터 개수 N = 5
summary = 0

for x in array:
	summary += x

print(summary)

⇒ 수행시간이 데이터 개수 N에 비례

⇒ O(N)

ex.

array = [3, 5, 1, 2, 4]  # 데이터 개수 N = 5

for i in array:
	for j in array:
		temp = i * j
		print(temp)

⇒ O(N**2)

(모든 2중 반복문이 O(N**2)의 시간복잡도를 가지는 것은 아님)

📍 알고리즘 설계 Tip

1. 일반적으로 연산 횟수가 5억을 넘기면, Python은 5~15초 소요

⇒ 코딩테스트 시간 제한: 1~5초

⇒ 시간 제한이 명시되어 있지 않은 경우, 대략 5초 정도라고 생각하고 풀기

2. Pypy가 때때로 C보다 빠름

⇒ Python 코드가 시간 초과 판정이 날 경우, Pypy로 재제출 해보기

3. 우선적으로 시간제한 확인하기

⇒ 데이터 개수를 N, 시간 제한이 1초인 경우

N ≤ 500 : O(N**3) 알고리즘 설계,

N ≤ 2000 : O(N**2) 알고리즘 설계,

N ≤ 100,000 : O(NlogN) 알고리즘 설계,

N ≤ 10,000,000 : O(N) 알고리즘 설계

📍 알고리즘 문제해결 과정

1. 지문읽기 및 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제 해결을 위한 아이디어 찾기
4. 소스코드 설계, 코딩

※ 핵심 아이디어 캐치 → 간결한 코드 작성 가능

📍 수행시간 측정 소스코드

import time

start_time = time.time()

### 소스코드 ###

end_time = time.time()

print("time: ", end_time - start_time)

📍 출처

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈