[Algorithm] 알고리즘과 복잡도

알고리즘: 처리 순서를 기술한 것

 

알고리즘 + 자료구조 = 프로그램

 

알고리즘을 공부해야하는 이유?

:  문제 해결 필요 

-> 여러 프로그램 중 어떤 것이 이 문제를 해결하는데 적합할지 판단 

-> 이 때 입력 데이터의 양,가용자원(cpu, 메모리) 등을 고려하여 어느 알고리즘을 선택할지 판단 

-> 그러기 위해서는 알고리즘의 성능, 평균 소모 시간, 최악/최선 소모 시간 등에 대해 알고 있어야 함

 

 

퀵 소트: 내부정렬 (메모리 상에서 정렬을 함) 알고리즘 중에서도 가장 고속

 

복잡도

: 일반적으로 복잡도에는 시간/공간이 있지만 그냥 복잡도 라고 하면 시간복잡도를 의미하며, 

최악/평균 복잡도가 있으나, 대부분의 알고리즘은 최악복잡도만 알면 충분

 

 

복잡도의 덧셈

복잡도 O(f(n)) , O(g(n)) 인 두 조작은 연속 실행했을 경우 복잡도

: O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

 

복잡도의 곱셈

복잡도 O(f(n)) 의 루프를 O(g(n)) 회 반복 실행했을 경우 복잡도

: O(f(n)) ∙O(g(n)) = O(f(n)g(n))

책. Java 프로그래머를 위한 알고리즘과 자료구조