[Algorithm] Time Complexity (시간 복잡도)

안자매 2022. 6. 22.

개인적으로 공부하면서 기록하는 공간으로
잘못된 정보는 댓글을 통해 알려주시면 감사하겠습니다 :-)

▪ ▪ ▪ ▪ ▪

어떤 목적을 달성하거나 문제를 해결하기 위한 여러 동작들의 모임으로, 연산, 데이터 진행 또는 자동화된 추론을 수행한다.

알고리즘의 조건

- 입력: 외부에서 제공되는 자료가 0개 이상 존재

- 출력: 적어도 2개 이상의 서로 다른 결과 출력

- 명확성: 수행과정은 명확하고 모호하지 않은 명령어로 구성

- 유한성: 유한 번의 명령어를 수행한 후에 종료

- 효율성: 모든 과정은 명백하게 실행 가능해야 함

복잡도는 알고리즘의 성능을 나타내는 척도로 크게 시간 복잡도와 공간 복잡도로 표현할 수 있다.

- 시간 복잡도: 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간과 입력의 함수 관계

- 공간 복잡도: 알고리즘에서 사용하는 메모리의 크기

점근 표기법

- 빅 오메가 표기법 (Big-Ω Notation) : 알고리즘 최상 실행 시간 표기

- 빅 세타 표기법 (Big-θ Notation) : 알고리즘 평균 실행 시간 표기

- 빅오 표기법 (Big-O Notation) : 알고리즘 최악의 실행 시간 표기

알고리즘이 최악일 때의 경우를 판단하면 평균과 가까운 성능으로 예측하기 쉽기 때문에 알고리즘의 효율성을 분석할 때 Big-O Notation 표기법을 가장 많이 사용한다.

Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때 연산 횟수에 대해 걸리는 시간을 표기하는 방법이다.

Big-O 표기법의 종류

O(1)

O(log n)

O(n)

O(nlog n)

O(n^2)

O(n^n)

O(1)	O(log n)	O(n)
일정한 복잡도(constant complexity)	로그 복잡도(logarithmic complexity)	선형 복잡도(linear complexity)

O(1)은 입력값이 증가하더라도 시간은 늘어나지 않음.	Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가짐	입력값이 증가함에 따라 시간도 같은 비율로 증가
O(nlog n)	O(n^2)	O(2^n)
로그 선형 복잡도 (log linear complexity)	2차 복잡도(quadratic complexity)	기하급수적 복잡도 (exponential complextiy)

대부분의 효율이 좋은 알고리즘이 이에 해당	입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가	실행시간은 입력의 크기에 따라 기하급수적으로 증가
O(n!)
팩토리얼 복잡도 (factorial complexity)

가장 느린 알고리즘으로 입력값이 조금만 커져도 계산하기 어려움