알고리즘 시간 복잡도

복잡도(Complexity)?

- 시스템이나 시스템 구성 요소 또는 소프트웨어의 복잡한 정도를 나타내는 말

- 시스템의 복잡도가 높으면 장애 발생 가능성이 높으니 정밀 테스트를 통해 미리 오류 제거할 필요성이 있음

- 시스템 개발에 소요되는 자원을 예측할 수 있음

 

시간 복잡도

- 알고리즘을 수행하기 위해 프로세스가 수행하는 연산 횟수를 수치화한 것

- 시간 복잡도가 낮을 수록 알고리즘 실행 시간이 짧고 높을 수록 길어짐

 

점근 표기법

- 시간 복잡도, 즉 프로세스 실행 횟수를 표기하는 표기법

- 빅오 표기법, 세타 표기법, 오메가 표기법

 

빅오 표기법(Big-O Notation)

- 알고리즘의 실행시간이 최악일 때를 표기하는 방법

 

O(1) : 입력값(n)에 관계 없이 일정하게 문제 해결에 단 하나의 단계만을 거침

O(log2n) : 문제 해결에 필요한 단계가 입력값(n) 또는 조건에 의해 감소

O(n) : 문제 해결에 필요한 단계가 입력값(n)과 1:1의 관계를 가짐

O(nlog2n) : 문제 해결에 필요한 단계가 입력값 n(log2n)번 만큼 수행

O(n^2) : 문제 해결에 필요한 단계가 입력값(n)의 제곱만큼 수행

O(2^n) : 문제 해결에 필요한 단계가 2의 입력값(n) 제곱만큼 수행

 

세타 표기법(Big-θ Notation)

- 알고리즘의 실행시간이 평균일 때를 표기하는 방법

 

오메가 표기법(Big-Ω Notaion)

- 알고리즘의 실행시간이 최상일 때를 표기하는 방법