Search

알고리즘 성능 평가

복잡도 (Complexity)

알고리즘의 성능을 나타내는 척도
시간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석
공간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석
→ 동일한 기능을 수행하는 알고리즘이라면, 복잡도가 낮을수록 좋은 알고리즘!

빅오 표기법 (Big-O Notation)

가장 빠르게 증가하는 항만 고려하는 표기법
함수의 상한만 나타냄.
연산 횟수가 3N³ + 5N² + 1,000,000인 알고리즘
차수가 큰 항만 남겨 O(N³)으로 표기
성능 순으로 나열한 알고리즘의 빅오 표기
O(1) : 상수 시간(Constant time)
O(logN) : 로그 시간(Log time)
O(N) : 선형 시간
O(NlogN) : 로그 선형 시간
O(N²) : 이차 시간
O(N³) : 삼차 시간
O(2ⁿ) : 지수 시간

알고리즘 설계 팁

코테 문제의 일반적인 시간제한 1~5초!
시간제한(수행시간) 요구사항 확인
시간제한이 1초인 문제의 경우 복잡도 선택 기준
N의 범위가 500 : 시간 복잡도 O(N³) 알고리즘
N의 범위가 2,000 : 시간 복잡도 O(N²) 알고리즘
N의 범위가 100,000 : 시간 복잡도 O(NlogN) 알고리즘
N의 범위가 10,000,000 : 시간 복잡도 O(N) 알고리즘
본 글은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성되었습니다. 다음의 컨텐츠들을 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.