[책] 누구나 자료구조와 알고리즘 - 7장 일상적인 코드 속 빅 오

 

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고

이번 장에서는 여러가지 상황에서 빅 오 표기법을 사용해 시간 복잡도를 계산하는 방법을 알려준다.

 

상황 1 : 짝수의 평균

문제: 배열에서 모든 짝수의 평균을 반환할 때의 빅 오 표기법을 사용해 시간 복잡도를 구한다.

 

평균 = 짝수의 합 / 짝수의 개수

메서드로 전달 된 수 배열 == 데이터 원소 N (N은 배열의 크기)

---

1. 짝수의 합, 짝수의 개수를 담을 변수를 각각 만든다. (2)
2. 루프를 돌면서 원소를 순회한다. (N)
   1. 짝수라면
      1. 짝수의 합에 더한다 (N)
      2. 짝수의 개수를 늘린다. (N)
3. 짝수의 평균을 구하기 위해 나누기를 수행한다. (1)

---

2.에서 최악의 경우 배열의 모든 수가 짝수가 되므로 3N이 성립된다.

계산 결과: 2 + 3N + 1

빅 오 표기법에서는 상수를 제외하므로

최종 결과를 빅 오로 나타내면: O(N)이다.

 

상황 2: 단어 생성기

문제: 문자 배열로부터 두 글자짜리 모든 문자열 조합을 모으는 알고리즘을 빅 오를 사용해 시간 복잡도를 구한다.

 

두 글자를 만들고 싶다면 중첩루프를 돌아 O(N^2)가 된다.

세 글자를 만들고 싶다면 루프를 한번 더 돌아 O(N^3)이 된다.

 

상황 3: 배열 예제

문제: 배열에서 3개를 추출해내고 싶다. 인덱스를 아는 상황이다.

 

요소 3개를 추출해내고 싶다면 O(3) 이지만 단계 수가 상수이고, 배열의 총 요소 개수(N)보다 작으므로 O(1)이 된다.

 

상황 4: 평균 섭씨 온도 구하기

문제: 섭씨로 받은 온도를 화씨로 바꾸고, 그 온도들의 평균을 계산하는 알고리즘을 빅 오를 사용해 시간 복잡도를 구한다.

 

1. N개짜리 배열을 화씨로 변경

2. 화씨로 바뀐 N개짜리 배열을 돌며 배열의 합을 구한다

 

상수를 제거한다면 O(N)이 된다.

 

상황 5: 의류 상표

2개의 조합

for 루프 array1 (의류 상표)

for 루프 개수 (5개)

 

처리할 주요 데이터는 의류 상표이기 때문에 여기서 N은 의류 상표의 개수이다.

O(N^2)로 착각할 수도 있지만, 개수는 5로 고정, O(5N)이 될 수 있지만 상수는 제거하기 때문에 O(N)이다.

 

상황 6: 1 세기

문제: 2차원 배열에서 각 배열의 크기의 합을 구하는 알고리즘을 빅 오를 사용해 시간 복잡도를 구한다.

주어진 2차원 배열 안의 배열들의 크기가 같지 않다.

{
	[0, 1, 0, 1, 0],
    [0, 0, 1, 0],
    [0, 1, 0]
}

이 때, 2차원 배열을 탐색하기 위해 이중 루프를 돌게 되어 시간 복잡도를 O(N^2)로 착각할 수 있다.

하지만 N은 요소의 개수이고 해당 알고리즘은 단순히 모든 수를 탐색하니 O(N)의 시간 복잡도를 가진다.

 

상황 7: 팰린드롬 검사기

문제: 주어진 문자열이 팰린드롬인지 검사하는 알고리즘을 빅 오를 사용해 시간 복잡도를 구한다.

팰린드롬이란 앞으로 읽으나 뒤로 읽으나 똑같은 단어 혹은 구절을 이야기 한다. (ex. kayak, racecar, deified)

 

이 때, 맨 앞의 글자와 맨 뒤의 글자를 동시에 비교하고, 문자열의 중간까지 비교했는데 동일하다면 true를 반환한다.

문자열의 반만 순회하며 비교하면 되기 때문에 시간 복잡도는 O(N/2), 상수를 제거하면 O(N)이 된다.

상황 8: 모든 곱 구하기

문제: 수 배열을 받아 모든 두 숫자 조합의 곱을 반환하는 알고리즘을 빅 오를 사용해 시간 복잡도를 구한다.

조건: 오른쪽에 있는 수만 곱한다.

N + (N-1) + (N-2) + ...... + 1

이 공식은 항상 N^2 / 2로 계산된다.

빅 오는 상수를 무시하므로 O(N^2)로 표시한다.

상황 8-1: 여러 데이터 세트 다루기

문제: 배열이 두개 주어졌을 때 (상황 8과 동일)수 배열을 받아 모든 두 숫자 조합의 곱을 반환하는 알고리즘을 빅 오를 사용해서 시간 복잡도를 구한다.

 

배열1의 크기(N), 배열2의 크기(M)을 곱한 값 O(N x M) 으로 표기할 수 있다.

이 때, 두 배열의 크기가 같다면 O(N^2)와 동등하고,

더 작은 수(이 수가 1만큼 작더라도)를 임의로 M에 할당하면 O(N)이 된다.

따라서 어떤 의미에서는 O(N x M)을 O(N)과 O(N^2)의 사이 정도로 이해할 수 있다.

 

상황 9: 암호 크래커

문제: 브루트 포스 방식으로 풀기로 하고, 주어진 길이의 모든 문자열 조합을 생성하는 코드를 작성하는 알고리즘을 빅 오를 사용해서 시간 복잡도를 구한다.

 

입력받는 변수 N이 문자열의 길이를 결정한다.

a-z까지의 문자열 조합을 만드는 것이고, 알파벳의 개수는 26이다.

때문에 N에 해당하는 문자열 길이의 모든 a-z조합을 만드는 단계의 총 조합 수는 26^N이 된다.

 

O(2^N)인 알고리즘 조차 엄청나게 느리다. (어떤 시점부터 O(N^3)보다 훨씬 느리게 된다.) 

O(2^N)의 반대는 O(logN)인데,

O(logN)인 알고리즘에서는 데이터가 두 배로 늘어날 때, 알고리즘에 한 단계씩 더 걸리는 반면에,

 O(2^N)인 알고리즘에서는 데이터가 한 개 늘어날 때 알고리즘에 필요한 단계가 두 배로 늘어나기 때문이다.

- O(26^N)인 경우에는 데이터가 한 개 늘어날 때 알고리즘에 필요한 단계가 26배로 늘어나게 됩니다.

 

때문에 26^N은 아아주 엄청나게 느린, 비효율적인 알고리즘이라고 할 수 있다.