03 복잡도
복잡도 프로그램의 실행 속도는 동작하는 하드웨어나 컴파일러 등의 조건에 따라 다르다. 알고리즘의 성능을 객관적으로 평가하는 기준은 복잡도(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개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 가장 높은 복잡도를 ..
2021.08.27