시간복잡도

- 빅 오 (O) : 최악일 때의 연산 횟수, 주어진(최선/최악/평균) 경우의 수행 시간의 상한

- 시간 복잡도 : 가장 많이 중첩된 반복문의 수행 횟수를 기준으로 

 

- 연산횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출

 

- 대부분의 경우 시간과 공간은 트레이드오프 관계 (실행시간이 빠른 알고리즘은 공간을 많이 사용) 

 

• O(1) : 입력값이 아무리 커도 실행 시간은 일정 (해시테이블의 조회 및 삽입)
• O(logN) : 로그는 매우 큰 입력값에도 크게 영향 받지 않는 편 (이진검색)
• O(N) : 입력값만큼 실행 시간에 영향, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례 (정렬되지 않은 리스트에서 최대/최솟값)
• O(NlogN) : 병합 정렬을 비롯한 대부분 효율 좋은 정렬 알고리즘
• O(N^2) : 버블 정렬 같은 비효율적인 정렬 알고리즘
• O(2^N) : 피보나치 수를 재귀로 계산하는 알고리즘
• O(N!) : 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제(Travelling Salesman Problem, TSP)를 부르트 포스로 풀이할 때 

 

 

 * python 프로그램 1초 : 2000만번~1억번 연산 (worst인 1초에 2000만번으로 기준) 

 

정렬:

- python A.sort(): O(NlogN)

- 버블 정렬 : O(N^2)

- 병합 정렬 : O(NlogN) 

 

탐색:

binary search : O(logN)

 

 

[ 입력 크기 확인 ]

- 원본 데이터는 그리 크지 않지만, 질의의 개수가 엄청 크다 ???

  >> 한번 정답판 만들어 놓고 질의가 오면 바로 답을 출력하는 형태 (가능성 높음)