알고리즘의 효율은 어떻게 측정해야 할까요?

세상에는 굉장히 많은 문제들이 있고 그 문제들을 해결하기 위한 알고리즘도 굉장히 많습니다.

문제 A를 해결하는 알고리즘 B와 C가 있다고 가정해 봅시다.

우리는 어떤 알고리즘을 선택해 문제를 해결해야 할까요?

단순히 알고리즘 B와 C 모두 구현해 보고 시간을 재 더 빠른 것을 선택하는 것도 방법이지만, 알고리즘을 구현하기 전에 어떤 알고리즘이 더 효율적인지 대략적으로 알 수 있으면 좋지 않을까요?

Big-O 표기법(Big-O notation)은 입력 데이터의 크기에 비례해 알고리즘의 효율성을 시간 복잡도로 판단하기 위해 등장했습니다.

---

Big-O 표기법

Big-O 표기법은 점근 표기접(Asymptotic notation)의 한 방법으로 실행 시간의 상한(Upper bound)을 표현합니다.

점근 표기법이란 입력 데이터의 크기가 무한대로 증가할 때 실행 시간이 어떠한 비율로 증가하는지 나타낸 것을 말합니다.

Big-O 표기법을 나타내기 위해서는 아래와 같은 단계를 거칩니다.

• 1단계에서는 수행되는 연산의 개수를 계산해 나타냅니다.

int Add1(int n) {

	return n + n;
    
} // 연산의 개수 : 1

int Add2(int n) {

	int sum = 0;
    
    for (int i = 0; i < n; i++)
    	sum += i;
        
	return sum
} // 연산의 개수 : n + 1

int Add3(int n) {

	int sum = 0;
    
    for (int i = 0; i < n; i++)
    	for (int j = 0; j < n; j++)
        	sum += 1;
            
    return sum;
} // 연산의 개수 : n^2 + 1

• 2단계에서는 영향력이 가장 큰 최고차항만 남기고 나머지 항은 삭제합니다. 최고차항에 붙는 상수 또한 삭제합니다.

int Add4(int n) {

	int sum = 0;
    
    for (int i = 0; i < n; i++)
    	sum += i;
        
    for (int i = 0; i < 2 * n; i++)
    	for (int j = 0; j < 2 * n; j++)
        	sum += 1;
            
    sum += 1234567;
    
    return sum;
} // 연산의 개수 : 4*n^2 + n + 2, O(n^2)

여기서 O는 Big-O 또는 Order of 라고 읽습니다.

Big-O 표기법의 의의

Big-O 표기법은 입력 데이터의 크기에 비례해 알고리즘의 효율성을 시간 복잡도로 나타낼 수 있으며, 이를 통해 효율적인 알고리즘을 사용할 수 있도록 도와줍니다.

대표적인 시간 복잡도

아래는 Big-O 표기법으로 나타낸 대표적인 시간 복잡도입니다.

• O(1) : 상수 함수(Constant function), 입력 크기와 무관하게 일정한 시간이 소요됩니다.

• O(logn) : 로그 함수(Logarithmic function), 입력 크기의 로그에 비레하는 시간이 소요됩니다. 대체로 매 단계마다 입력의 크기를 절반으로 줄여가는 형태로 동작하며, 대표적으로 이진 탐색 알고리즘이 있습니다.

• O(n) : 선형 함수(Linear function), 입력의 크기에 비례하는 시간이 소요됩니다.

• O(nlogn) : 로그-선형 함수(Log-linear function), 대부분 효율적인 정렬 알고리즘의 시간 복잡도가 로그-선형 함수를 따릅니다. 대표적으로 퀵 정렬 알고리즘이 있습니다.

• O(n^2) : 이차 함수(Quadratic function), 보통 2중 반복문을 사용하는 알고리즘의 경우 시간 복잡도가 이차 함수를 따릅니다. 대표적으로 버블 정렬, 선택 정렬, 삽입 정렬 알고리즘이 있습니다.

• O(n^3) : 삼차 함수(Cubic function), 보통 3중 반복문을 사용하는 알고리즘의 경우 시간 복잡도가 삼차 함수를 따릅니다.

• O(2^n) : 지수 함수(Exponential function), 일반적으로 시간 복잡도가 지수 함수 이상을 따르는 경우 아주 작은 입력 데이터를 가진 경우에만 사용할 수 있으며, 그 외 경우에는 대부분 비효율적이므로 사용할 수 없습니다.

• O(n!) : 팩토리얼 함수(Factorial function)

Big-O 표기법으로 나타낸 시간 복잡도의 활용

문제 해결 계획을 세우고 구현하기 전에 시간 복잡도를 따져보고 문제의 제한사항을 만족하는지 대략적으로 판단해 볼 수 있습니다.

---

포스팅을 마치며

이번에는 Big-O 표기법에 대해 공부한 내용을 정리해 봤습니다.
알고리즘 문제 풀이에 대한 직관이 생기기 전까지는 검증 과정에서 Big-O 표기법으로 시간 복잡도를 계산해 봐야겠네요.

Reference

• Rookiss. C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈 Part3 : 자료 구조와 알고리즘. Inflearn.
• 황선규. C++ 어서와! 자료 구조와 알고리즘은 처음이지?. Programmers.
• Michael T. Goodrich, et. al. Data Structures and Algorithms in C++ 2nd Edition. Wiley, 2011.