알고리즘 시간복잡도란 무엇인가?

알고리즘 시간복잡도는 무엇일까? 알고리즘 문제 풀이하는 사람들이 품을 수 있는 궁금증이라고 생각합니다. 

 

 

◆ 시간복잡도의 정의

 

알고리즘 시간복잡도란 어떤 알고리즘에 대해서 입력 개수(N)에 비례하여 걸릴 수 있는 시간, 실행 횟수를 수치화 시켜서 비교할 수 있는 데이터로 만든 값입니다.

네이버에서 검색한 결과는 아래와 같습니다.

 

어떤 알고리즘이 더 빠른가 즉, 명령어 실행 횟수가 더 적은가를 분석하기 위해 사용되는 시간 복잡도는 알고리즘을 평가하기 위한 중요한 요소 중 하나입니다.

 

 

이제 무엇인지는 알 것 같다는 느낌이 들 것 입니다. 

 

 

 

◆ 시간복잡도 표기법

 

이제는 시간복잡도에 대한 표기 방법에 대해서 설명드리겠습니다.

 

표기 방법은 아래와 같습니다.

 

O({알고리즘 입력 개수(N)에 비례하여 실행되는 횟수 계산 값})

 

여기서 () 안에 들어가는 값은 입력 개수(N)로 표현할 수 있는 수식입니다.

예로 1, logN, N, N * logN, N² 등 다양한 N과 관련 수식으로 표현할 수 있습니다.

 

 

 

 

◆ 시간복잡도 계산 방법

 

알고리즘 시간복잡도를 구하는 방법에 대해서 간단한 예시로 들어서 설명해보겠습니다.

 

 

아래는 숫자 10이라는 값을 number라는 변수에 대입하는 것을 코드로 구현한 것입니다.

 

const number = 10;

 

위 코드의 시간복잡도를 구하기 전에 실행 횟수를 간단하게 세어볼까요?

실제로는 number라는 변수를 담을 메모리를 생성하고, number라는 변수가 담긴 메모리에 10의 값을 대입하는 등 컴퓨터는 실제 몇 차례의 실행을 거쳐서 수행을 하게 될 것입니다. 하지만 사람이 볼 때 이 코드의 실행 횟수는 간단하게 "number라는 변수에 10을 대입한다"라는 대입 연산으로 실행 횟수는 1번으로 계산할 수 있습니다.

이 때, 실행 횟수가 1번 즉, 계산할 수 있는 "상수"의 횟수를 통해 이루어지는 알고리즘을 O(1)의 시간복잡도를 갖는다라고 표현합니다.

 

 

그럼 O(1)의 시간복잡도를 갖는 알고리즘은 무엇이 있을까요?

반복 없이 일차원적으로 이루어지는 계산 및 비교, 출력, 입력 등 단순한 연산들 대부분 O(1)의 시간복잡도를 갖는다고 생각하시면 편할 것 같습니다.

 

 

 

 

그럼 이번에는 반복문의 시간복잡도를 계산해보도록 하겠습니다. 그러기 위해서는 간단한 반복문 코드를 구현해보겠습니다.

 

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

for(let i = 0; i < array.length; i++) {
	console.log(array[i]);
}

 

위 코드는 정말 간단한 배열의 항목들을 반복문 내에서 Index 0부터 9까지 순서대로 출력하는 코드입니다. 그럼 이 코드에 대한 시간복잡도는 어떻게 될까요?

먼저 array를 선언하고 값을 입력하는 부분은 O(1)의 시간복잡도를 갖는 것으로 위에서 공부해보았습니다. 그러면 for문 즉, 반복문 내에서의 동작에 대한 시간복잡도를 계산해보도록 하겠습니다.

1. i가 0부터 array.length보다 작을 때까지 순차적으로 1씩 증가하는 실행을 수행합니다.
2. 순차적으로 i가 증가한 이후 array의 i번째 인덱스 값을 콘솔로 출력합니다.

위 두가지 실행이 array의 길이만큼 반복하게 될 것입니다. 즉, 입력 값의 길이만큼 반복하게 되는 것입니다. 여기서 언급된 입력 값의 길이를 N이라 칭하면 위 실행 횟수는 N * 2 = 2N 만큼 수행할 것입니다. 바로 2N 중 2는 상수 값이므로 어떤 값이 오든 비례하여 고정되어 증가하지만, N은 변할 수 있는 변수로 이 실행 횟수에 직접적인 영향을 주는 값입니다. 이렇게 반복문을 통해 입력 값의 길이(N)만큼 반복하는 동작을 수행하는 알고리즘의 시간복잡도를 O(N)이라고 말합니다.

 

 

 

 

◆ 시간복잡도 표기의 해석

 

위에서 두 가지의 예시 코드에 대한 시간복잡도 표기의 의미를 알아보았습니다. 그럼 전반적으로 표현할 수 있는 알고리즘의 시간복잡도 표기의 해석에 대해 이해하는 시간을 가져보려고 합니다.

 

 

O(1)	해당 코드는 Input의 길이(N)과 연관 없는 코드이다.
O(logN)	해당 코드는 Input의 길이(N)에 비례하여 logN 정도의 시간이 걸리는 코드이다.
O(N)	해당 코드는 Input의 길이(N)에 비례하여 N 정도의 시간이 걸리는 코드이다.
O(NlogN)	해당 코드는 Input의 길이(N)에 비례하여 N * logN 정도의 시간이 걸리는 코드이다.
O(N2)	해당 코드는 Input의 길이(N)에 비례하여 N2 정도의 시간이 걸리는 코드이다.

---

 

 

위 처럼 Input의 길이와 실행 횟수가 연관이 있다면 N을 활용하여 표기할 수 있습니다. logN은 실제 입력 값의 개수보다 적은 실행 횟수를 통해 결과를 얻을 수 있는 알고리즘이라는 것이며, N²은 실제 입력 값의 개수에 제곱한 만큼의 실행 횟수를 통해 결과를 얻을 수 있는 알고리즘이라는 것이다.

 

 

 

 

◆ 알고리즘 별 시간복잡도

 

마지막으로 많이 활용하는 대표 알고리즘들에 대한 시간복잡도를 알아보도록 하겠습니다.

 

 

• 배열
  • 탐색
    • 일반 검색: O(N)
    • 이진 탐색: O(logN) - 정렬되어있는 배열에서만 가능
  • 정렬
    • 퀵 정렬: O(NlogN)
    • 버블 정렬, 삽입 정렬: O(N²)
  • 추가, 삭제: O(N)
• 해시 맵
  • 생성: O(N)
  • 탐색: O(1)
  • 추가, 삭제: O(1)

 

 

 

 

오늘은 알고리즘 시간복잡도에 대한 기초를 알아보았습니다. 처음 보시는 분께서는 정말 어려운 단어로 받아들여 이해가 어려우셨을 수도 있지만, 제 글을 포함해서 여러 글을 읽어보시면서 개발자가 되시고 싶으신 분들이라면 한번 쯤 알고 가는 기회가 되셨으면 합니다.