[개념 콕] 시간복잡도와 공간복잡도

내일배움캠프 수료생이 개발에 꼭 필요한 핵심 개념만 콕 집어 드립니다.

May 29, 2024

Contents

시간 복잡도 공간 복잡도 빅오 표기법 (Big-O)내일배움캠프는 개발에 필요한 핵심만 배웁니다

✍🏼

개발을 시작하시는 여러분, 정보가 너무 많고 배워야 할 것도 산더미라 어디서부터 시작해야 할지 막막하신가요? 내일배움캠프 수료생들이 4개월 동안 배운 엄선된 핵심 개념을 직접 정리해서 알려 드립니다. 공부하다 막히거나 헷갈리는 개념이 있다면 개념 콕으로 정리해보세요.

복잡도란?

복잡도란 알고리즘의 효율성을 객관적으로 비교하고 판단할 수 있는 기준을 제시하는 개념입니다. 즉, 해당 알고리즘이 얼마나 효율적인지 판단하는 척도입니다.

시간 복잡도는 알고리즘의 수행 시간에 중점을 두는 척도로, 입력 크기에 따라 알고리즘이 얼마나 빠르게 동작하는지를 나타냅니다. 반면 공간 복잡도는 알고리즘이 사용하는 메모리 용량에 초점을 맞춘 척도로, 입력 크기에 따라 알고리즘이 얼마나 많은 메모리를 필요로 하는지를 나타냅니다.

시간 복잡도

시간 복잡도는 특정 크기의 입력을 기준으로 알고리즘을 수행하는 데 필요한 연산의 횟수를 나타냅니다. 비록 '시간'이라는 단어가 사용되지만, 실제로는 연산의 횟수를 세는 것이 더 정확한 방법입니다. 그 이유는 다음과 같습니다.

첫째, 동일한 알고리즘을 다양한 운영체제(OS), 통합 개발 환경(IDE), 플랫폼에서 실행할 경우 일관된 결과를 얻기 어렵습니다. 예를 들어, C언어, C++, Java 등 서로 다른 프로그래밍 언어로 동일한 알고리즘 문제를 해결하더라도 각 언어별로 실행 시간이 상이하게 나타날 수 있습니다.

둘째, 알고리즘의 성능을 평가하기 위해서는 실행 시간을 측정하는 대안적인 방법이 필요합니다. 예를 들어, Java에서는 다음과 같은 방식으로 실행 시간을 측정할 수 있습니다.


// 코드 실행 전에 시간 받아오기
long beforeTime = System.currentTimeMillis();

// 실행할 코드 작성
...
...
...

// 코드 실행 후 시간 받아오기
long afterTime = System.currentTimeMillis();

// 두 시간의 차 계산
long resultTime = (afterTime - beforeTime) / 1000

System.out.println("시간차이(m) : " + resultTime);

시간 복잡도를 평가할 때는 다양한 경우를 고려해야 합니다. 일반적으로 다음과 같은 세 가지 경우를 분석합니다. 아래의 세 가지 경우를 종합적으로 분석함으로써, 해당 알고리즘의 전반적인 성능과 효율성을 객관적으로 평가할 수 있습니다.

1) 최선의 경우 (Best Case)

입력된 데이터가 알고리즘에 가장 유리한 상태로 주어졌을 때, 작업을 완료하는 데 필요한 연산 횟수가 가장 적은 경우를 말합니다. 이는 알고리즘의 최상의 성능을 나타냅니다.

2) 최악의 경우 (Worst Case)

입력된 데이터가 알고리즘에 가장 불리한 상태로 주어졌을 때, 작업을 완료하는 데 필요한 연산 횟수가 가장 많은 경우를 말합니다. 이는 알고리즘의 최하의 성능을 나타냅니다.

3) 평균의 경우 (Average Case)

다양한 입력 상태를 고려하여, 전체 연산 횟수를 모든 경우의 수로 나눈 평균값을 나타냅니다. 이는 알고리즘의 전반적인 성능을 평가하는 데 사용됩니다.

공간 복잡도

공간 복잡도는 알고리즘을 실행하고 완료하는 데 필요한 메모리의 양을 나타냅니다. 알고리즘 실행에 필요한 공간은 크게 두 가지로 나눌 수 있습니다.

1) 알고리즘 자체와는 무관한 고정 공간

여기에는 코드 자체가 저장되는 공간과 알고리즘 실행을 위해 시스템이 필요로 하는 공간이 포함됩니다.

2) 알고리즘과 밀접하게 관련된 가변 공간

이는 문제를 해결하기 위해 알고리즘이 사용하는 공간으로, 변수를 저장하는 공간이나 재귀 프로그램의 경우 재귀 호출을 위한 스택 공간 등이 해당됩니다.

그렇다면 알고리즘의 성능을 평가할 때 시간 복잡도와 공간 복잡도 중 어느 것을 더 중요하게 고려할까요? 일반적으로 시간 복잡도를 더 우선적으로 고려합니다.

빅오 표기법 (Big-O)

알고리즘의 복잡도를 표현할 때 자주 사용되는 방법 중 하나가 바로 빅오 표기법(Big-O Notation)입니다. 빅오 표기법은 알고리즘의 효율성을 상한(upper bound)을 기준으로 표현하기 때문에 최악의 경우를 고려하는 데 적합합니다. 알고리즘 분석 시 평균적인 경우와 최악의 경우가 주로 활용되는데, 알고리즘이 복잡해질수록 평균값을 구하기 어려워지므로 최악의 경우를 기준으로 알고리즘의 성능을 파악하는 것이 일반적입니다.

빅오 표기법은 다음과 같이 표기하는 방식입니다.

복잡도	소요시간	특징
O(1)	상수 시간	입력 크기에 관계없이 일정한 시간이 소요되는 가장 효율적인 알고리즘
O(logN)	로그 시간	ㅤ
O(N)	직선적 시간	ㅤ
O(N log N)	선형 로그 시간	ㅤ
O(N^2)	2차 시간	ㅤ
O(2^N)	지수 시간	입력 크기가 조금만 증가해도 실행 시간이 기하급수적으로 증가하므로 가장 비효율적인 알고리즘

시간 복잡도는 상수 → 로그 → 직선적 → 선형 → 2차 → 지수 순으로 효율성이 평가됩니다. 즉, 상수 시간 알고리즘은 입력 크기에 관계없이 일정한 시간이 소요되는 가장 효율적인 알고리즘입니다. 반면에 지수 시간 알고리즘은 입력 크기가 조금만 증가해도 실행 시간이 기하급수적으로 증가하므로 가장 비효율적인 알고리즘이라고 할 수 있습니다.

그림으로 표현하면 다음과 같습니다.

알고리즘을 설계하고 구현할 때는 가능한 한 낮은 시간 복잡도를 가지도록 노력해야 합니다. 이를 통해 알고리즘의 효율성을 높이고, 큰 입력에 대해서도 빠르게 동작하는 프로그램을 작성할 수 있습니다.

내일배움캠프는 개발에 필요한 핵심만 배웁니다

지금까지 꼭 필요한 개발 지식에 대해 알아보았습니다. 내일배움캠프에서는 전문가들이 선별한 핵심 개발 지식으로 개발 공부도, 취업도 보다 효율적으로 할 수 있는데요. 국내 유수의 IT기업 출신 튜터님들과 실습 위주의 독보적인 커리큘럼으로 개발자 취업을 체계적으로 준비해보세요. 내일배움캠프 4개월, 여러분 인생의 가장 큰 터닝 포인트입니다.

CREDIT

글 | 황규정 내일배움캠프 수료생 편집 | 정효재 팀스파르타 에디터