day41 🌕

장미·2022년 7월 24일

오늘의 성과

목록 보기

41/129

스프링 MVC 1편 - 백엔드 웹 개발 핵심 기술 섹션 7 마저 수강 및 완강

+) 22. 07. 27. day40 🌕 에 추가 완료 🔪

토픽 - 시간 복잡도, 공간 복잡도

+) 22. 07. 29. 추가 완료 🔥

프로그램을 만들 때 우리는 다양한 알고리즘을 사용한다.
예를 들어, 정수를 오름차순으로 정렬하는 프로그램을 만든다고 가정하면 버블 정렬, 삽입 정렬, 퀵 정렬 등 여러 가지 알고리즘을 사용할 수 있다.
결과는 같지만 어떤 알고리즘을 쓰느냐에 따라서 과정이 달라진다. 즉, 알고리즘마다 성능도 제각각 다르다.
이 때 우리는 가장 좋은 성능을 발휘하는 알고리즘을 사용하고 싶을 것이다. 아니, 사용해야 한다.

가장 좋은 알고리즘을 고르기 위해선 효율성을 따져야 한다.

시간적 효율성 → 이 알고리즘이 얼마나 빠른지 → 시간 복잡도
공간적 효율성 → 이 알고리즘이 메모리를 얼마나 차지하는지 → 공간 복잡도

같은 데이터를 입력해도, 알고리즘마다 수행하는 시간이 다르고 차지하는 공간이 다르다.

보통은 공간 복잡도보다 시간 복잡도를 더 우선시한다. (기술력이 점점 좋아져서 메모리의 성능이 좋아지고 있기 때문에 우리는 시간 복잡도를 더 우선으로 고려하면 된다.)

알고리즘의 속도는 입력 데이터가 n개일 때 CPU의 연산 횟수로 판단한다. (알고리즘의 속도에 영향을 미치는 것은 여러 이유가 있겠지만 가장 큰 원인은 연산 횟수이다.)
→ 입력 데이터의 양이 다르다면 당연히 데이터가 많은 쪽이 더 오래 걸린다. 그러므로 데이터는 똑같이 n이라 가정하고 연산 횟수로 비교한다.

Big O

여기서 ‘빅오’에 대한 개념이 등장한다.
O(N)은 입력이 N일 때 연산 횟수 혹은 차지하는 메모리 양이 얼마나 되는지를 나타낸다.

만약 f(n) = 99999n + 9999, g(n) = 0.00001n² 이 있다면 이 때 f(n)은 O(n), g(n)은 O(n²)으로 표기한다.

속도의 빠른 순은 다음과 같다. (오른쪽으로 갈수록 느리다.)

O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > O(2^N) > O(N!)

O(1)은 배열의 요소를 참조할 때, O(logN)은 이진 탐색, O(N)은 순차 탐색, O(NlogN)은 퀵 정렬, O(N^2)은 버블 정렬, O(2^N)은 피보나치 수열(재귀함수)의 속도가 된다.

O(1)

입력값의 크기에 상관없이 일정한 시간이 소요된다.

void function(int[] arr) {
	System.out.print(arr[3]);
}

arr의 크기가 백만이어도 arr[3]을 출력하는 시간은 정해져 있다.

O(logN)

입력값의 크기의 절반씩 검색량이 감소한다. (Binary Search)

위 숫자 중에서 13을 찾을 경우, 먼저 총 숫자 개수인 8개의 절반을 나눈다.
그럼 딱 절반에 있는 수는 23이 된다. 이 때 13은 23보다 작기 때문에 23과 그 오른쪽 숫자들은 더 이상 고려할 필요가 없다. 그냥 날려버리면 된다.

그럼 이제 여기서 절반값인 16과 13을 비교하면 된다.
13이 더 작기 때문에 16, 19는 날려버리고 13, 15만 안고 가면 된다.

여기서 15와 13을 비교하면 13이 더 작기 때문에 왼쪽으로 간다.
그리고 13을 드디어 찾게 되었다.

→ 총 8개의 숫자를 3번만 비교하여 값을 찾았다. (log8 = 3 → logN 만큼 소요)

O(NlogN)

입력값의 크기 만큼 반으로 나누고, 다시 그 개수만큼 비교한다. (Merge Sort, Quick Sort, Heap Sort)

Merge Sort의 경우 아래 숫자들을 계속 반씩 나눈다.

최종적으로 값이 하나씩 남을 때까지 말이다.
그리고 하나씩 값을 비교한다.

6과 5를 비교해서 오름차순 정렬

| 5 | 6 |
3과 1을 비교해서 오름차순 정렬

| 1 | 3 |
반복…

결과는 | 5 | 6 | | 1 | 3 | | 7 | 8 | | 2 | 4 | 이렇게 될 것이다.

그럼 이제 5와 1을 비교해서 오름차순으로 정렬한다.
그리고 3과 5를 비교(→ 135), 3과 6을 비교(→ 1356), 7과 2를 비교 후 7과 4 비교(→ 247), 4와 8을 비교(→ 2478)한다.

이렇게 반복하다 보면 개수만큼 비교해서 합치게 된다.
(반으로 나눌 때 logN, 합병할 때 N만큼 비교 → O(NlogN) 소요)

O(N^2)

입력값의 크기에 따라 소요되는 시간이 제곱으로 증가한다. (Bubble Sort, Insertion Sort, Selection Sort)

Bubble Sort

void BubbleSort(int[] arr) {
	for(int i = 0; i < arr.length; i++) {
		for(int j = 0; j < arr.length - i - 1; j++) {
			if(arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
			}
		}
	}
}

여기서 파란 화살표를 i, 노란 화살표를 j라 하자.
처음에는 둘 다 0번째니까 두 화살표 모두 3에 가있을 것이다. 이 때 arr[j] = 3, arr[j+1] = 1이므로 두 수를 비교하면 1이 더 작으니 1과 3의 위치를 스왑한다.
그리고 파란 화살표 i는 그대로 0번째 자리에 있고, 노란 화살표 j만 다음 인덱스로 움직인다.