2장 : 시간 복잡도

 

입력 크기에 비례하는 것 / 알고리즘의 실행 시간 & 데이터의 상관관계

통상 1초가 넘어가면 안됨

 

-

 

통상 배열(for문 선형 탐색) -> O(N)

 

-

단순 연산 : O(1)

 

이진 : O(logN)

선형 : O(N)

정렬 : O(N logN)

조합 : O(2^N)

순열 : O(N!)

 

-

 

입력 조건에 명시된 최악의 경우를 시간 복잡도에 대입 -> 1억이 넘지 않으면 통상 Ok (시간제한 1초시)

 

-

 

시간 제한이 없더라도 대부분의 코드는 10초 내에 실행 완료 (10억이 넘어가면 안됨)

 

-

 

길이 N 정수로 이루어진 배열 -> M개의 숫자 유무

10,000개 / 100,000개

 

최악 -> 10억

이진 탐색 -> O((N+M)logN)

HashSet -> O(M+N)

 

-

 

상수, 곱하기, 사칙연산은 고려되지 않는다

 

-