알고리즘 이론 정리

복잡도

1) 시간 복잡도 : 계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계(수행 시간)

[참고: 위키피디아]

 

2) 공간 복잡도 : 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양(메모리 양)

[참고: wiki.hash.kr/index.php/공간복잡도]

 

복잡도가 더 낮을수록 좋음

 

Big-O Notation

 - 가장 빠르게 증가하는 항만을 고려하는 표기법

 - 연산 횟수가 $5N^3 + 2N^2 + 3N^1 + 100$인 알고리즘이 있으면 Big-O Notation에서는 $O(N^3)$으로 표기

   (계수 무시)

 

[참고 : www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=1]

 

상수 시간	O(1)
로그 시간	O(logN)
선형 시간	O(N)
선형 로그 시간	O(NlogN)
2차 시간	O($n^2$)
3차 시간	O($n^3$)
지수 시간	O($2^n$)

위로 갈수록 복잡도가 더 낮고 아래로 갈수록 복잡도가 더 높다.

[참고 1 : www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=1]

[참고 2 : ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84]