복잡도
프로그램의 실행 속도는 동작하는 하드웨어나 컴파일러 등의 조건에 따라 다르다.
알고리즘의 성능을 객관적으로 평가하는 기준은 복잡도(Complexity)다.
1. 시간 복잡도(Time Complexity): 실행에 필요한 시간을 평가한 것
2. 공간 복잡도(Space Complexity): 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
선형검색 알고리즘의 복잡도
1, 4, 6의 경우, 한번만 실행하기 때문에 복잡도를 O(1)으로 표기
2, 3, 6의 경우, 평균 실행 횟수는 n/2이다. 복잡도를 O(n)으로 표기
O(n)에 필요한 계산 시간은 n에 비례하여 점점 길어진다.
O(1)에 필요한 계산 시간은 변하지 않는다.
2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 가장 높은 복잡도를 선택한다,
O(1) + O(n) + O(n) + O(1) + O(n) + O(1) = O(max(1, n, n, 1, n, 1)) = O(n)
선형 검색 알고리즘의 복잡도는 O(n)이다.
이진 검색의 시간 복잡도
O(1) + O(1) + O(log n) +O(log n) + O(1) + O(log n) ... + O(1) = O(log n)
이진 검색 알고리즘의 복잡도는 O(n)이다.
복잡도와 증가율
