[CS] 시간복잡도와 공간복잡도

 

알고리즘을 풀다보면 마주할 수 있는 복잡도(Complexity)와 빅오 표기법(Big-O notation)에 대해 항상 들어왔고 중요성을 인지하고 있지만 너무 추상적인 개념이었기에 정리를 시도해보려한다.

💣복잡도란?

복잡도란 다음과 같이 정의할 수 있다.

1. 알고리즘의 성능 및 효율성을 나타내는 척도
2. 크게 시간복잡도(Time-Complexity)와 공간복잡도(Space-Complexity)로 나눌 수 있다.
3. 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시한다.
4. 복잡도를 나타내는 방법으로는 점근 표기법 기준으로 O(빅오), Ω(오메가), Θ(세타) 등이 있고, 주로 빅오와 세타 표기법이 많이 사용된다.

• 점근 표기법 : 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법 으로 알고리즘에선 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다. 이중 표기법 중 빅오 표기법이 존재한다.

정리: 복잡도란 해당 알고리즘이 얼마나 효율적인지를 판단하는 척도

👊🏻 시간 복잡도 vs 공간 복잡도

시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)이 필요한지를 판단한다.

시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단한다.

하지만 적절한 중간점을 찾는 것이 중요하기에 각각에 대한 자세한 설명과 더불어 각 자료구조및 메소드가 가지는 복잡도에 대해 살펴보자

🅾️ 빅오 표기법 (Big-O notation)

빅오 표기법(Big-O notation)은 복잡도를 나타내는 접근 표기법 중 많이 사용되는 표기법이다.

빅오 표기법이 가장 많이 사용되는 이유는 알고리즘 효율성을 상한선 기준으로 표기하기에 최악의 경우를 고려하는데 가장 좋은 표기법이다. (알고리즘 효율성은 값이 클수록, 즉 그래프가 위로 향할수록 비효율적임을 의미)

📉빅오 표기법의 수학적 정의

빅오 표기법의 수학적 정의는 다음과 같다.

O(g(n))={f(n) : there exist positive constants c and $ n_0 $ such that 0≤f(n)≤cg(n) for all n≥$n_0 $}

 

 

n0를 기준으로 n0보다 오른쪽에 있는 모든 n 값에 대해 f(n)은 함수 cg(n)보다 같거나 작다는 의미이다. - 점근적 상한선

즉 빅오 표기법에서는 주어진 알고리즘이 아무리 나빠도 비교하는 함수와 같거나 좋다. 그래프가 아래있을 수록 수행시간이 짧아 성능이 좋은 것

🕹 빅오 표기법 특징

1. 상수항 무시
   • 빅오 표기법은 n이 충분히 크다고 가정하고 있고 알고리즘의 효율성은 n의 크기에 영향을 받으므로 상수항 같은 사소한 부분은 무시한다.
   • O(2n)은 O(n)으로 간주
2. 영향력이 없는 항은 무시한다.
   • 빅오 표기법은 수 N의 크기에 영향을 받기 때문에 가장 영향력이 큰 항 이외에 영향력이 없는 항은 무시
   • O(n^2 + 2n +1)은 O(n^2)로 간주
   • 다만 n보다 큰값은 표기에 들어간다.

⌚ 시간복잡도(Time-complexity)

• 코드가 얼마나 빠르게 작동하냐를 수치화 시킨 것
• 시간복잡도가 커지면 코드는 느려지고 시간복잡도가 낮을수록 코드는 빨라진다.
• 알고리즘에 사용되는 총 연산횟수를 의미
• 어떤 알고리즘 안에서 연산을 몇번 수행하는가이며 진행되는데 걸린 시간이 아니다.

정리 : 특정 크기의 입력값에 대해 알고리즘 적용시 필요한 연산의 횟수

시간복잡도 예시

public class Main{
	public static void main(String[] args) {
		int sum=0; //할당 시 연산 1번
		for (int i=0;i<5;i++){
				sum+=i; //총 연산 4회
		}	
	}
}

// 시간복잡도 1+4=5회

만약 이중포문이라면?

public class Main{
	public static void main(String[] args) {
		int sum=0; //할당 시 연산 1번
		for (int i=0;i<5;i++){
				for(int j=0;j<5;j++){
						sum+=i*j; //4*4 =16
			}
		}	
	}
}
// 총 시간복잡도 1+16=17회

이렇게 loop를 많이 이용할 수록 시간복잡도가 기하급수적으로 증가하여 이런 이유로 효율적인 알고리즘이 탄생하게 되었다.

여기서 알고리즘이 조금 더 복잡해진다면?

우선 두가지의 전제조건을 가지고 다른 예시 코드를 살펴보자.

• 입력 변수의 크기가 N으로 주어진다.
• 코드의 시간복잡도는 f(N)이다. ⇒ N에 대해서만 작동되는 함수이다.

public List<Integer> doNothing(List<Integer> numbers){
		return numbers; //1
}

/*
함수의 이름에서도 직관적이게 느낄 수 있듯 아무것도 하지않고 반환만 하는 함수이다.
numbers의 크기가 N으로 주어졌을때 이 메소드의 시간복잡도는 1이다.

return 연산자체는 시간복잡도를 1로 정의한다. 추후 Big-O에서 다시한번 설명한다.
*/

 

public int isN(List<Integer> numbers){
		int sum=0; //1번
		for(int num:numbers){
				sum+=num; //N번
		}
		
		return sum; //1번
}

	// 총 시간복잡도 N+2

 

public List<Integer> isNComplexity(List<Integer> numbers){
		List<Integer> all_list=new ArrayList<>();//1번
		
		for(int i=0;i<numbers.length;i++){ //for문 안에 for문 중첩이므로 N * N
				for(int k=0;k<numbers.length;k++){ 
					if(numbers.get(i)<numbers.get(k)){ //1번
						all_list.add(numbers.get(k)); // if-else 구문 중 하나가 실행되므로 1번
					}else{
						all_list.add(numbers.get(i));
					}
			}
		}		
		return all_list; //1번
}

	// 총 시간복잡도 2*N^2 + 2

 

시간복잡도인데 연산횟수를 계산하는 것은 왜일까?

그 이유는 다음과 같다.

1. 모든 OS와 IDE에서 동일한 결과를 산출한다는 보장이 없다.
2. 실행시간과 측정은 환경에 따라 달라질 수 있다.

 

⏰ 시간 복잡도는 왜 중요할까?

잘 와닿지 않을 수 있지만 시간복잡도가 다른 코드 1,2를 서로 비교해보며 알아보자

아래와 같은 조건을 가진 코드가 존재한다고 가정한다.

코드1 코드2

시간 복잡도	1,000N	2N^2
Big-O	O(N)	O(N*2)

 

이때 N은 고정된 값이 아니기에 알고리즘을 어떻게 구현하냐에 따라 시간복잡도가 확연히 달라지게 된다.

N 1 10 100 1,000 10,000 …

 

코드 1	1,000	10,000	100,000	1,000,000	10,000,000	1000 * …
코드 2	2	200	20,000	2,000,000	200,000,000	2 * … ^2

 

N이 1,10,100일 때에는 코드 1의 시간복잡도가 훨씬 큰데 N이 증가함에 따라두코드간의 시간복잡도가 줄어들더니 코드2의 시간복잡도가 코드1보다 기하급수적으로 증가하게 되는 모습을 볼 수 있다.

해당 모습을 그래프로 보면 다음과 같다.

 

 

0~20까지는 별로 차이가 심하지 않지만 N의 크기가 증가하면 증가할 수록 각 알고리즘의 복잡도에 따라 차이가 편이하다. 그렇기 때문에 우리는 알고리즘을 구현할 때 N의 크기는 상당히 큰 값이 들어온다고 가정하고 구현해야한다.

Big-O 시간복잡도 계산 법칙

1. for/while loop 가 한번 중첩될 때마다 O(N)

private void isList(List<Integer> num_list){
		for(int x: num_list){
				log.info(x);
		}
}
// 이때 List의 크기가 N이라고 가정하였을 때
// Big-O 시간복잡도는 O(N)이다

 

private void isLoopOfLoop(List<Integer> num_list){
		for(int index1:num_list){
				for(int index2:num_list){
						log.info(index1*index2);
				}
		}
}

/*
	Big-O 시간복잡도는 O(N*N)이기 때문에 O(N^2)이다.
*/

 

private void isLoopOfThree(List<Integer> num_list){
		for(int index1:num_list){
				for(int index2:num_list){
						for(int index3:num_list){
								log.info(index1*index2*index3);
						}
				}
		}
}

// Big-O 시간복잡도는 O(N*N*N)이기 때문에 O(N^3)이다.

2. 자료구조를 사용하거나 다른 함수를 호출할 땐 각각의 O(N)을 파악

private void justArray(){
	int [] arr= {1,2,3,4,5};
	List<Integer> numberList=Arrays.asList(arr);
	if(numberList.contains(2)) 
}

// Big-O 시간복잡도 O(N)

 

private void justArray(List<Integer> numbers){
	Collections.sort(numbers);
}

// Big-O 시간복잡도 O(NlogN)

3. 매번 절반씩 입력값이 줄어들면 O(logN)

 

 

이진 탐색을 예시로 들었을 때 매번 실행할 때 마다 배열의 크기가 반씩 줄어들기 때문에 N의 크기가 8일때 총 실행 수는 log8=3이된다.

시간복잡도 BP와 WP

• 🥇최선의 경우 (Best Case)
  최적의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 적은 경우
• 🥉최악의 경우 (Worst Case)
  최악의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 많은 경우
• 🥈보통의 경우 (Average Case)
  여러 경우의 수를 고려하여, 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우

정리 : 알고리즘 분석 시 평균과 최악의 경우를 가장 많이 활용하고 알고리즘이 복잡해질수록 평균을 구하는 것이 어려워 최악의 경우로 알고리즘의 성능을 파악하는 경우가 많다.

✨ 시간복잡도와 빅오 표기법

시간 복잡도는 특정 크기의 입력(n)을 기준으로 실행하는 연산의 횟수이다. 다시 말해 연산의 횟수를 세면 된다.

그렇다면 알고리즘이 실행될 때의 모든 연산의 횟수를 세어야 하는가?답은 아니다. 알고리즘에서 핵심이 되는 연산의 횟수만 세면 된다.

 

시간복잡도와 예시

복잡도 소요 시간 예시

O(1)	상수 시간	스택에서 Push, Pop
O(log n)	로그 시간	이진 트리
O(n)	직선적 시간	for 문
O(n log n)	선형 로그 시간	퀵 정렬(quick sort), 병합 정렬(merge sort), 힙 정렬(heap sort)
O(n^2)	2차 시간	이중 for 문, 삽입 정렬(insertion sort), 거품 정렬(bubble sort), 선택 정렬(selection sort)
O(C^n)	지수 시간	피보나치 수열

 

 

상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수

왼쪽에서 오른쪽으로 갈수록 성능이 떨어지며, 시간 복잡도가 좋지 않은 알고리즘이다.

 

시간복잡도를 구하는 요령

• 하나의 루프를 사용하여 단일 요소 집합을 반복하는 경우 : O(n)
• 컬렉션의 절반 이상을 반복하는 경우: O(n / 2) -> O(n)
• 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복하는 경우: O(n + m) -> O(n)
• 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우: O(n²)
• 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복하는 경우: O(n * m) -> O(n²)
• 컬렉션 정렬을 사용하는 경우: O(n*log(n))

🎪 공간 복잡도

• 코드가 얼마나 많은 메모리를 사용하는지를 수치화 시킨 것
• 공간복잡도가 커지면 메모리를 많이 차지하고 공간복잡도가 낮아지면 메모리를 적게 차지
• 공간복잡도가 체크되는 기준은 프로그램의 실행부터 완료까지이다.
• 알고리즘을 실행하기 위해 필요한 공간(Space)의 정의는 두가지로 나뉜다.
  1. 알고리즘과 무관한 공간, 고정 공간이라 칭함
     • 코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간 등
  2. 알고리즘과 밀접한 공간, 가변 공간이라 칭함
     • 문제를 해결하기 위해 알고리즘이 필요로 하는 공간으로 변수의 저장 또는 순환 프로그램의 한해 순환 스택(recursion stack) 등

Big-O 공간복잡도 예제

private void instatnceAllocation(){
	int a=1;
}
//Big-O 공간복잡도는 O(1)

 

private void loop(List<Integer> nums){
		for(int num1:nums){
				...
		}
}
//Big-O 공간복잡도는 O(N)

 

private void loopTwice(List<Integer> nums){
		for(int num1:nums){
				for(int num2: nums){
						...
				}
		}
}
//Big-O 공간복잡도는 O(N^2)

✨ 공간복잡도와 빅오 표기법

공간 복잡도는 알고리즘 실행에 메모리가 얼마나 사용되는지 계산하면 된다.

예를 들어 크기가 n인 List가 입력으로 주어졌을 경우 알고리즘이 n*n의 이중 List를 생성한다면 해당 알고리즘의 공간 복잡도는 n^2이다

알고리즘의 공간복잡도를 계산 후 불필요한 상수항 또는 영향력이 없는 상수항을 제거하면 그것이 알고리즘의 총 공간복잡도에 대한 빅오표기법이된다.

공간 복잡도는 보통 중요하게 생각하지 않는 경우가 많지만, 많은 데이터를 다루는 경우 공간 복잡도가 커지게 되면 프로그램이 메모리에 올라가지 않아 실행할 수 없게 될 수도 있다.

따라서 알고리즘 작성 시 공간 복잡도도 어느 정도 신경 써서 작성하는 것이 좋다

📘 Big-O 표기법으로 나타낸 자료구조별 시간 복잡도

📙 Big-O 표기법으로 나타낸 정렬 알고리즘별 복잡도