정리내용은 [이것이 취업을 위한 코딩 테스트다 with 파이썬] 책을 기반으로 작성하였습니다.
이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고
취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드 | 이런 독자에게 권합니다.■ IT 직군의 취업 준비생 / 예비 개발자■ 이직을 준비하는 개발자■ 알고리즘 대회를 준비하는 학생[특징]코딩
www.kyobobook.co.kr
복잡도
성능을 나타내는 척도를 말한다. 시간복잡도와 공간복잡도로 나뉜다. 복잡도가 낮을수록 좋은 알고리즘이다.
과거에는 메모리의 가격이 비싸고, 하드웨어 성능에 한계가 있었기 때문에 얼마나 더 적은 공간을 사용하는 지가 중요했지만, 시간이지나면서 하드웨어의 성능이 크게 증가했고, 현재는 공간 복잡도보단 시간 복잡도가 조금 더 중요한 요소로 여겨진다.
시간복잡도와 공간복잡도는 일종의 거례고나계가 성립된다. 메모리를 조금더 많이 사용하는 대신 반복되는 연산을 생략하거나, 더 많은 정보를 관리하면서 계산 복잡도를 줄여 시간을 줄이는 방법이 있다.(메모제이션 기법)
시간복잡도
특정 크기의 입력에 대해 알고리즘이 얼마나 오래걸리는지 의미
알고리즘을 위해 필요한 연산의 횟수
코딩테스트에서는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행결과를 출력하는데 까지 걸리는 시간을 의미한다.
공간복잡도
특정 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지 의미
알고리즘이 필요한 메모리의 양
코딩 테스트는 대부분 128~512MB로 제한한다.
Big-O 표기법
복잡도를 표현할 때는 빅오표기법을 사용한다.
| 빅오표기법 | 명칭 |
| O(1) | 상수시간 |
| O(logN) | 로그시간 |
| O(N) | 선형시간 |
| O(NlogN) | 로그선형시간 |
| O(N^2) | 이차시간 |
| O(N^3) | 삼차시간 |
| O(2^n) | 지수시간 |
[ex] N = 1000 일 경우,O(N)=1000 / O(NlogN)=10,000 / O(N^2)=1,000,000 / O(N^3)=1,000,000,000 연산 실행
'Programming > 알고리즘 & 자료구조' 카테고리의 다른 글
| [알고리즘][이코테] 구현(Implementation) (0) | 2022.03.11 |
|---|---|
| [알고리즘][이코테] Greedy Algorithm(그리디 알고리즘) (2) | 2022.03.10 |
| [알고리즘] recursive function(재귀함수) (0) | 2022.03.08 |
| [자료구조] Graph(그래프) (0) | 2022.03.08 |
| [자료구조] Complete Binary Tree(완전이진트리) 와 Heap(힙) (0) | 2022.03.07 |