[기초내용] 시간 복잡도(Time complexity)

자료 구조와 알고리즘 관련 내용을 정리하고 봐야 할 경우가 자주 생기고

무시하고 갈 수 없는 상황이라

구글 검색을 바탕으로 옛 기억을 꺼내 보고자 한다.

알고리즘의 기초만 정리하자면

• 시간복잡도 - CPU 사용량에 대한 계산
• 공간복잡도 - RAM 사용량에 대한 계산
• 여러가지 표기법이 있지만 빅오 표기법이 가장 많이 사용
• 계산법이 중요 , 
• cpu 의 실제 실행 시간이 아닌 실행 횟수를 계산
• 계산법은 간다하게
•  명령어의 실행 횟수를 계산해서 최고차항을 이용
• O(n), O(logn) , O(n²) .... 등등으로 표기

지루하고 자세한건 위키백과 에서 확인 가능하다.

내가 볼때 중요한 것은 O(logn) 이다. 온라인 코딩 테스트도 이부분을 많이 물어보는 듯 하다.

logn은 로그형 시간으로 시간이 지남에 따라 연산이 줄어드는 것을 말한다.

말로 표현하면 이해가 가지만 실제 실제 코딩에 사용하기엔 생각을 많이 해야 한다.

결국 소스를 보면서 분석해야 하는데

가장 참고할만한 것은 이진 탐색 알고리즘이다. 

이진탐색의 기본 내용은

1. 전체 데이터를 정렬
2. 정렬 된 데이터를 반으로 나누어서 좌우를 각각 탐색
3. 해당 데이터가 없는 경우 다시 좌우의 비교할 데이터를 변경하여 탐색
4. 원하는 값을 찾을 때 까지 "3"을 계속 반복
5. 탐색 종료 
6. 주로 재귀호출을 사용( 난 재귀호출 싫어함)

내가 찾아본 바로는 여기가 가장 쉽게  잘 정리되어 있는 듯 하다.

응용 문제 

• let data_arr = new Array(28, 44, 3, 10,98,1209874)

• 위에 주어진 배열을 키 집합을 만든다 (ex : (0,0) , (0,1) , (0,2) .......... (4,0) , (4,1) ..... )

• 키 집합의 각 값의 사이에 data_arr 배열의 값이 있는 경우의 키 집합을 골라 내기

• 최악의 시간복잡도는 O(n * logn )

• 내가 사용한 방식은 다음 언젠가 포스팅에..

참고 사이트 추가

• http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/
• https://gist.github.com/TSiege/cbb0507082bb18ff7e4b
• https://codility.com/programmers/