복잡도 (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 파이썬’을 읽고 공부한 내용을 바탕으로 작성되었습니다.
다음의 컨텐츠들을 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.
