[이것이 취업을 위한 코딩테스트다 with Python] chapter 01 코딩 테스트 개요

복잡도

• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미
• 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미

 

시간 복잡도

• 빅오(Big-O) 표기법 사용
• 빅오 표기법 : 가장 빠르게 증가하는 항만을 고려하는 표기법, 함수의 상한만을 나타낸다.

• 일반적인 코딩 테스트에서 O(N^3) 을 넘어가면 문제 풀이에서 사용하기 어렵다.
• 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 C언어를 기준으로 통상 1초 이상의 시간 소요된다.
• N의 크기가 5,000이 넘는다면 10초 이상의 시간이 걸릴 수 있다.
• 코딩 테스트 문제에서 시간 제한은 1~5초 가량이므로 보통 연산 횟수가 10억을 넘어가도록 작성하면 오답 판정을 받을 수 있다.
• 시간 복잡도에서 '연산'은 사칙연산, 비교연산 등과 같은 기본 연산을 의미하고 더하기, 빼기 같은 사칙 연산 뿐만 아니라 비교연산 또한 한 번의 연산으로 취급 

 

공간 복잡도

• 빅오 표기법을 이용한다.
• 메모리 사용량에도 절대적인 제한이 있다.
• 일반적으로 메모리 사용량 기준은 MB단위로 제시된다.
• 코딩 테스트에서 보통 메모리 사용량을 128~512MB 정도로 제한한다. 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다.

빅오 표기법	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^N)	지수 시간

위 내용은 <이것이 취업을 위한 코딩테스트다 with 파이썬>을 기반으로 공부하여 작성 내용입니다.

http://www.yes24.com/Product/Goods/91433923

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