복잡도

복잡도는 시간 복잡도와 공간 복잡도로 나뉜다.

목차

• 시간 복잡도
• 공간 복잡도
• 자료 구조에서의 시간 복잡도

시간 복잡도

C++의 기본

시간 복잡도에 대해 알아보기 전에, C++의 기본을 살펴보자.

먼저 아래는 입력 받은 문자열을 출력하는 프로그램이다.

#include <iostream>						// -- (1)

std::string input;						// -- (2)

int main(int argc, char **argv) {		// -- (3)
	std::cin >> input;					// -- (4)
	std::cout << input << std::endl;	// -- (5)
	return 0;							// -- (6)
}

C++은 C에서 파생된 언어로, C의 기본적인 문법을 대부분 계승하고 있다. C와 마찬가지로 C++도 컴파일 언어이기 때문에, 프로그램을 실행하기 위해서는 컴파일 과정을 거쳐야 한다.

컴파일은 크게 전처리, 컴파일, 어셈블, 링크의 4단계로 이루어진다.

1. 전처리: #include와 같은 전처리 지시자를 처리한다. (위 코드의 -- (1) 부분)
2. 컴파일: 전처리된 코드를 어셈블리어로 번역한다.
3. 어셈블: 어셈블리어를 기계어로 번역한다.
4. 링크: 여러 개의 오브젝트 파일을 하나의 실행 파일로 합친다.

라이브러리 코드 병합, 전역 변수 초기화 등이 컴파일 과정에 일어나고, 코드가 컴파일 되고 프로그램이 실행되면 main 함수가 호출된다. (위 코드의 -- (3) 부분) main 함수는 프로그램의 시작점으로, 하나의 main 함수가 반드시 존재해야 한다. 프로그램은 main 함수의 명령을 순차적으로 실행하며, main 함수가 프로그램의 종료 상태를 반환하며 종료된다.

코드에 각 부분에 대해 설명을 덧붙이면 다음과 같다.

1. #include <iostream>: 입출력 스트림을 사용하기 위한 헤더 파일을 포함한다.
2. std::string input;: 문자열을 저장하기 위한 전역 변수를 선언한다. <타입> <변수명> 형태로 변수를 선언한다. std::string my_first_string = "Hello World!";와 같은 변수가 있다고 할 때, my_first_string은 lvalue, "Hello World!"는 rvalue라고 한다. lvalue는 메모리 주소를 가지는 값을 의미하며, rvalue는 메모리 주소를 가지지 않는 값을 의미한다.
3. int main(int argc, char **argv): 프로그램의 시작점인 main 함수를 정의한다. argc는 명령행 인자의 개수, argv는 명령행 인자의 값을 담고 있는 배열이다.
4. std::cin >> input;: 표준 입력으로부터 문자열을 입력받아 input 변수에 저장한다.
5. std::cout << input << std::endl;: input 변수에 저장된 문자열을 표준 출력으로 출력한다.
6. return 0;: 프로그램의 종료 상태를 반환한다. 0은 정상 종료를 의미한다.

빅오 표기법

시간 복잡도란 입력 크기에 따른 알고리즘의 실행 시간을 나타내는 척도이다. 주요 로직의 반복 횟수를 중점으로 측정되며, 보통 빅오 표기법(Big O Notation)으로 표현된다.

아래의 별 찍기 프로그램을 예로 들어보자.

#include <iostream>						// -- (1)

int main(int argc, char **argv) {		// -- (2)
	int n;								// -- (3)
	std::cin >> n;						// -- (4)

	for (int i = 0; i < n; i++) {		// -- (5)
		for (int j = 0; j <= i; j++) {	// -- (6)
			std::cout << "*";			// -- (7)
		}
		std::cout << std::endl;			// -- (8)
	}
	return 0;							// -- (9)
}

위 코드에서 별을 찍는 부분은 -- (5)부터 -- (8)까지이다. n이 5라고 가정했을 때, 별을 찍는 부분의 실행 횟수는 다음과 같다.

• i = 0: 1회
• i = 1: 2회
• i = 2: 3회
• i = 3: 4회
• i = 4: 5회
• 총합: 1 + 2 + 3 + 4 + 5 = 15회

따라서, 별을 찍는 부분의 실행 횟수는 $n(n + 1) / 2$로 표현할 수 있다. 이는 Big O 표기법으로 $O(n^2)$로 표현된다. Big O 표기법에서는 실행 횟수에 가장 큰 영향을 미치는 항만 고려한다. 이는 n이 충분히 커질 때 다른 항들의 영향이 상대적으로 작아지기 때문이며, 수학적 극한의 개념을 함께 생각해보면 더 쉽게 이해할 수 있다.

시간 복잡도의 존재 이유

시간 복잡도는 알고리즘의 효율성을 평가하고 코드를 개선하는 데 중요한 척도로 사용된다. 게시물을 시간 순으로 정렬하여 최근 게시물을 화면에 표시하는 프로그램이 있다고 가정해보자. 게시물을 정렬 하는 데에 걸리는 시간이 $O(n^2)$이고, 한 명령을 처리하는데 1ms가 걸린다고 하자. 게시물이 1000개라면, 화면이 나타나는 데 걸리는 시간은 약 1초이다. 하지만, 게시물이 10,000개라면, 화면이 나타나는 데 걸리는 시간은 약 100초가 된다. 이 프로그램을 $O(n \log n)$ 알고리즘으로 개선한다면, 게시물이 10,000개일 때 화면이 나타나는 데 걸리는 시간은 약 0.1초가 된다. 따라서, 시간 복잡도를 이해하고 최적화하는 것은 사용자 경험을 향상시키는 데 매우 중요하다.

시간 복잡도 그래프

공간 복잡도

공간 복잡도는 프로그램이 실행되는 동안 필요한 메모리의 양을 나타내는 척도이다. 시대가 발전함에 따라 메모리의 가격이 저렴해지고, 메모리 용량이 증가함에 따라 공간 복잡도의 중요성이 다소 줄어들었지만, 여전히 중요한 개념이다. 특히 게시판, SNS, 뉴스피드, 게임, 영상 스트리밍 서비스 등 대용량 데이터를 처리하는 애플리케이션에서는 공간 복잡도가 중요한 역할을 한다. 이는 페이스북, 트위터, 인스타그램의 성공·실패 사례에서 알 수 있듯이, 공간 복잡도를 고려하지 않은 설계는 서비스의 성능 저하와 사용자 경험 악화로 이어질 수 있기 때문이다.

시간 복잡도는 성능에 영향을 미치지만, 공간 복잡도는 안정성에 영향을 미치기 때문에, 더욱 신중하게 고려할 필요가 있다. 메모리 부족은 프로그램의 비정상 종료, 성능 저하, 데이터 손실 등의 매우 심각한 문제를 초래할 수 있다. 특히, 메모리 누수는 이를 확정적으로 일으킬 수 있는 대표적인 문제이므로 주의해야 한다.

자료 구조에서의 시간 복잡도

자료 구조를 선택할 때, 시간 복잡도를 고려하는 것은 매우 중요하다.

예를 들어, 배열과 연결 리스트는 모두 데이터를 저장하는 자료 구조이지만, 특정 작업에 대한 시간 복잡도가 다르다. 배열은 인덱스를 통해 빠르게 접근할 수 있지만, 삽입과 삭제는 느리다. 반면, 연결 리스트는 삽입과 삭제가 빠르지만, 인덱스를 통한 접근은 느리다. 따라서, 특정 작업에 대한 시간 복잡도를 고려하여 적절한 자료 구조를 선택하는 것이 중요하다.

보통 시간 복잡도를 생각할 때, 평균 시간 복잡도와 최악 시간 복잡도를 함께 고려한다.

자료 구조의 평균 시간 복잡도

자료 구조의 최악 시간 복잡도