알고리즘 - 시간 복잡도, 공간 복잡도, 빅오(O)표기법

참고

https://youtu.be/6Iq5iMCVsXA

http://ledgku.tistory.com/33

복잡도

시간 복잡도(time complexity) : 어떠한 연산을 수행하면서 사용한 시간을 나타낸다
공간 복잡도(space complexity) : 사용한 메모리의 사용량
복잡도는 보통 빅오(대문자 O) 표기법을 사용하며, 알고리즘 평가 사이트는 빅오 표기법으로 기준을 제시하고 최악의 경우로 평가 한다.
그리고 시간 복잡도가 괜찮으면 공간 복잡도는 어느정도 봐주는 경향이 있다.

time complexity

배열에서 특정 원소를 찾는 경우 

O(1)	인덱스로 바로 찾는 경우	int result = numbers[0];
O(n)	for 문 한번 돌려서 찾는 경우	for(int num : numbers) result = num;
O(n^2) 제곱	for 문을 두번 돌리면	for( ... ) { for ( ... ) { 연산 } }
O(log n) 로그	정렬된 배열에서 값을 찾는 경우	중간에 반씩 잘라서 비교해서 나머지는 버리면 되므로 logN 만큼 소요

n^2 이상이 되면 거의 통과 하기 어려우므로, O(n log n) 이하로 수행 될 수 있도록 프로그래밍 합니다.
quick sort, merge sort 공부하시면 개념이해에 좋습니다.
https://youtu.be/7BDzle2n47c

space complexity

공간 복잡도란 프로그램을 실행하는데 필요한 메모리의 양을 말하며,
보통 가변 공간만 체크하게 됩니다. 고정 공간은 코드 저장 공간, 변수/상수, 고정구조변수 를 말하며 N 이 커져도 변하지 않으므로 무시됩니다.
가변 공간은 보통 입력 인수에 대해서는 계산하지 않으므로
간단하게 보면, N 개의 배열이 입력되었을 때 추가로 int[] arr = new int[N] 과 같이 생성하면 O(N) 으로 보면 되겠습니다.