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

시간복잡도와 공간복잡도

효율적인 알고리즘이란, 알고리즘이 수행을 시작해 결과가 도출될때까지 실행에 걸리는 시간이 짧고 컴퓨터 자원을 덜 사용하는것이 효율적인 알고리즘이라고 말할 수 있습니다.

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)는 알고리즘의 효율성을 분석하고 측정하는 데 중요한 개념입니다. 시간 복잡도는 알고리즘의 실행 속도를 분석하며, 공간 복잡도는 알고리즘이 사용하는 메모리 공간의 크기를 분석합니다. 컴퓨터과학에서 이 둘은 '점근적 표기법' 을 이용해 함수식으로 표현합니다.

점근적 표기법

점근(漸近)이란?

- 점근(漸近): 점점 가까워지는 모양
- 점근적 표기법

1. 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법
2. 주워진 함수가 있을때, 보다 간단한 함수로 만들어 표시하는 것

알고리즘의 실행 시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존합니다. 이 속도는 알고리즘이 실행되는 소프트웨어와 하드웨어의 환경에 의존적입니다. 이렇게 환경에 의존적인 알고리즘을 속도로만 평가할 수 있을까요?

알고리즘의 실행 시간에 대해 두 부분으로 나누어 생각해 볼 수 있습니다.

1. 입력값의 크기에 따른 알고리즘의 실행 시간
2. 실행 시간의 성장률

1번, 입력값의 크기에 따른 알고리즘의 실행 시간은 직관적으로 이해가 가능합니다. 배열의 크기가 커지면 선형검색과 이진 검색의 최악으로 추측되는 연산 횟수가 커진다는 사실이라던가, 지도에서 길찾기를 할 때 탐색해야 할 길들이 골목길까지 포함하는게 아니라 오직 고속도로만 탐색한다는 조건을 걸면 더욱 길을 빠르게 찾을 수 있다는 사실로 이를 알 수 있습니다.

2번, 실행 시간의 성장률은 입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지 알아보는 것을 의미합니다. 이를 알기 위해선 알고리즘에서 중요하지 않은 부분은 버리고 가장 중요한 부분만 추려내어 함수를 간소화해야 합니다.

입력값이 n인 알고리즘이 n^2+2n 이라는 계산을 수행한다고 가정해봅시다. 해당 식에서 입력값 n이 커짐에 따라 기하급수적으로 커지는 부분은 n^2인것을 알 수 있습니다. 이런 식으로 중요하지 않은 항과 상수 계수를 제거하면 해당 알고리즘의 이해를 보다 쉽게할 수 있습니다.

위와 같이 중요하지 않은 항목을 제거하여 어떠한 것을 표현하는 것을 점근적 표기법 이라 합니다.해당 점근적 표기법에는 3가지의 형태가 있습니다. big-Θ(Theta) 표기법, big-O 표기법, big-Ω(Omega) 표기법입니다. 알고리즘을 평가할때는 이런 점근적 표기법을 이용해 시간복잡도와 공간복잡도를 나타냅니다. (일반적으로는 Big O가 사용됩니다.)

시간 복잡도

Big O 표기법: 최악의 경우를 가정한 표기법

가장 표준적으로 사용되는 빅오(Big-O) 표기법입니다. 빅오 표기법은 알고리즘의 최악 실행 시간을 고려하여 표기합니다.

// O(1)
// O(4)처럼 보이지만, 상수는 신경쓰지 않음.
function print_somthing(arr){
		console.log(arr[0]);
		console.log(arr[0]);
		console.log(arr[0]);
		console.log(arr[0]);
}

// O(n)
// O(3n)처럼 보이지만, 상수는 신경쓰지 않음.
function print_somthing(arr){
		for(let val of arr ){
			console.log(val);
		}
		for(let val of arr ){
			console.log(val);
		}
		for(let val of arr ){
			console.log(val);
		}
}

http://devwebcl.blogspot.com/2016/12/big-o-comparison.html, https://medium.com/thedevproject/logarithm-complexity-vs-linear-complexity-f9871333756b

Big-O 표기법	설명	예시
O(1)	상수 시간	스택에서 Push, Pop 등
O(log n)	로그 시간,기본적인 2는 상수이기에 제외하고 표기	이진 검색 등
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(2^n)	지수 시간	피보나치 수열 등

❗그러나 언제나 Big O가 모든 알고리즘을 완벽하게 설명하는것은 아닙니다.

이것에 대한 예시로, 버블정렬과 선택정렬을 비교해볼 수 있습니다. 둘은 같은 O(n^2)의 시간복잡도를 가지지만 둘 중 더 나은 정렬은 선택정렬 입니다. 둘은 전체 배열을 탐색하고, 특정 배열 요소들을 스왑하고, 비교도 진행하지만, 요소를 스왑하는 횟수는 선택정렬이 버블정렬보다 현저하게 적습니다. 선택정렬은 언제나 배열을 탐색하는 전체의 사이클 중 한번만 스왑을 하지만, 버블정렬은 최악의 경우 배열의 길이 -1 번 만큼 스왑을 하는 상황이 생길 수도 있습니다.

https://www.youtube.com/watch?v=Bor_CRWEIXo

---

공간 복잡도

공간 복잡도는 알고리즘의 메모리 사용량이 입력 크기에 대해 어떻게 증가하는지를 분석하는 것입니다. 추가적인 공간 사용 없이 입력 데이터만으로 문제를 해결할 수 있는 경우, 공간 복잡도는 O(1)이 됩니다. 그렇지 않은 경우, 공간 사용이 필요한 만큼 복잡도가 증가합니다.

시간 복잡도와 유사하게 big O 표기법을 사용해 점근적으로 표시됩니다.

면접 질문

Q1. 시간 복잡도는 무엇인가요?

시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 측정하는 방법으로, 알고리즘의 입력값 크기에 기반한 수행 시간을 함수로 표현한 방법입니다.

Q2. Big O 표기법이란 무엇인가요?

빅오 표기법은 알고리즘의 최악 실행 시간을 고려하여 표기하는 방법입니다.

Q3. 컴퓨터과학에서 알고리즘을 평가할때 왜 Big O표기법이 일반적으로 사용되나요?

최대의 입력 상태에서 최악의 상황을 고려하여 알고리즘을 설계를 하는 것이 부작용을 방지할 수 있기 때문입니다.

Q4. 프론트엔드 개발에서 시간 복잡도는 어떤 상황에서 중요하게 작용할까요?

첫째, 대규모 데이터를 처리할 때입니다. 대규모 데이터를 다룰 때는 처리 시간이 길어지면 사용자 경험이 나빠지게 되므로, 이를 최적화해야 합니다. 예를 들어, 검색 기능을 구현할 때 사용자가 입력한 검색어와 일치하는 항목을 찾는 작업에서 검색어가 많아질수록 처리 시간이 증가하므로 이를 최적화해야 합니다.

둘째, 애니메이션과 같은 인터랙티브한 요소를 다룰 때입니다. 이러한 요소는 사용자와의 상호작용을 통해 동적으로 변경될 수 있기 때문에, 매우 빠른 속도로 렌더링되어야 합니다. 이를 위해 최적화된 알고리즘을 사용하고, 불필요한 렌더링을 피해야 합니다.

 

출처

빅오 표기법 (big-O notation) 이란

 

[알고리즘] 시간복잡도(Time Complexity)와 Big-O표기법(Big-O Notation)

개발자라면 이제는 알아야하는 Big O 설명해드림. 10분컷.

Sorting Algorithms in JavaScript

 

⭐ 구글 클래스룸에서 제공하는 컴퓨터과학 수업. 컴공 대학 수업을 기반으로 작성된 강의이기도 하고, 이해하기 쉽게 설명 + 확인 문제도 있어서 추천드려요.

알고리즘이란 무엇이며, 왜 중요한가요? (동영상) | 알고리즘이란? | Khan Academy