알고리즘 성능 평가 개념 정리

빅O 표기법

2중 반복문의 시간 복잡도가 항상 O(N^2)인 것은 아니다.
소스코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려해야한다.

알고리즘 설계 TIP

일반 적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우)

1. C언어를 기준으로 통상 1~3초 가량의 시간이 소요됩니다.
2. PYTHON을 기준으로 통상 5~15초 가량의 시간이 소요됩니다.
   (PYPY의 경우 때때로 C언어보다도 빠르게 동작하기도 한다)

코딩 테스트 문제에서 시간제한은 통상 1~5초 가량이라는 점에 유의하세요
혹여 문제에 명시되어 있지 않은 경우 대략 5초 정도라고 생각하고 문제를 푸는 것이 합리적이다.

만약 PYTHON이 1초에 5000만번 정도 계산한다고 가정하에, O(N^3)의 알고리즘을 설계한 경우 N이 5000이 넘는다면 얼마나 걸릴까?

-> 5000의 3제곱은 1250억 연산횟수, 파이썬에서는 2500초가 걸린다. 이런식으로 설계 차원에서 생각을 하여야한다. 채점 서버에서는 파이썬이 1초에 2000만번 정도 된다라고 가정하고 문제에 입장해야한다.

요구사항에 따라 적절한 알고리즘 설계하기

알고리즘 문제 해결 과정

일반적인 알고리즘 문제 해결 과정은 다음과 같다.
1. 지문 읽기 및 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제 해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩

수행 시간 측정 소스코드 예제

import time
start_time = time.time()

end_time - time.time()
print(end_time - start_time)