알고리즘[시간복잡도]

시간복잡도란?

우리는 일상생활에서 거의 알고리즘을 사용한다

예를들어 출퇴근할때 어떻게가야 효율적으로 갈수있을지 생각하는것도 알고리즘이라고 할 수 있다.

이때 우리가 중요하게 생각하는것이 "속도"다. 

 

시간복잡도란 "입력값과 연산수행시간의 상관관계를 나타내는 척도" 를 말한다

즉, "문제를 해결하는데 걸리는 시간과 입력의 합수관계"이다.

 

시간복잡도 표현방법?

점근적 표기법으로 시간복잡도를 나타내는데, 아래 3가지가 있다

• 최상의 경우 : 오메가 표기법 (Big-Ω Notion)
• 평균의 경우 : 세타 표기법 (Big-θ- Notion)
• 최악의 경우 : 빅오 표기법 (Big-O Notion)

평균인 세타표기법을 사용하는것이 가장 좋다고 생각할 수도 있는데, 평가하기 까다롭다고한다.

시간복잡도는 최악을 기준으로 "빅오 표기법"으로 판단하여 성능을 예측한다.

오히려 알고리즘이 최악일때의 경우를 판단하면, 평균과 가까운 성능으로 예측하기 쉽다

 

 

빅오 표기법(Big-O Notion)?

빅오 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게할 목적으로 사용된다

Big-O 복잡성에는 시간복잡도와 공간복잡도가 있다

 

• 시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다
• 공간복잡도는 알고리즘이 실행될때 사용되는 메모리의 양을 나타낸다

요즘에는 데이터를 저장할 수 있는 메모리가 많이 발전해서 공간복잡도의 중요성은 낮아졌다

 

 

https://www.bigocheatsheet.com/

 

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

실행시간은 컴퓨터의 하드웨어 또는 프로그래밍 언어에 따라서 달라질 수 있기때문에, 실행시간이 아닌 연산횟수를 기준으로 수치화를 한것이다.

 

시간복잡도는 이렇게 최악을 기준으로 "빅오 표기법"으로 표시하여 성능을 예측하는데,

시간복잡도가 빠른순으로 보면 아래와 같이 나타낼 수 있다

O(1) < O(log n) < O(n) < O(n log n) < O(n^2)

 

O(1) : 문제를 해결하는데 오직 한단계만 처리
O(log n) : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬
O(n) : 문제를 해결하기위한 단계의수와 입력값 n이 1:1관계를 가짐
O(n log n) : 문제를 해결하기위한 단계의수가 N*(log2N)번 만큼의 수행시간을 가짐
O(n^2) : 문제를 해결하기위한 단계의수는 입력값 n의 제곱