이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다.
다양한 빅오 카테고리
단어 생성기
이 예제는 문자 배열로부터 두 글자짜리 모든 문자열 조합을 모으는 알고리즘이다.
예를 들어, [a,b,c,d]라는 배열이 주어지면 다음과 같은 문자열 조합을 포함하는 새 배열을 리턴한다.
아래는 이 알고리즘을 자바스크립트로 구현한 코드이다.
이 알고리즘의 효율성은 바깥 루프는 N개 원소를 모두 순회하고 각 원소마다 안쪽 루프는 다시 N개 원소를 모두 순회하니 O(N²)이다.
세 글자짜리 모든 문자열 조합을 계산하도록 알고리즘을 수정하면 함수는 아래와 같은 배열을 반환할 것이다.
function wordBuilder(array) {
let collection = [];
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
for(let k = 0; k < array.length; k++) {
if (i !== j && j !== k && i !== k) {
collection.push(array[i] + array[j] + array[k]);
}
}
}
}
return collection;
}
이 알고리즘은 중첩 루프가 총 3개 있으며, 3개 모두 N개의 원소를 순회하니 총 단계는 N x N x N = N³단계가 걸린다.
따라서 이를 빅 오 표기법으로 나타내면 O(N³)이다.
샘플 채취
배열에서 소규모 샘플을 취하는 함수를 생성한다.
아주 큰 배열이라 생각하고 맨 앞과 가운데, 맨 뒤 값을 샘플링한다.
def sample(array):
first = array[0]
middle = array[int(len(array) / 2)]
last = array[-1]
return [first, middle, last]
데이터의 개수는 배열의 원소 수이다.
하지만 이 함수는 배열의 원소 수(N)와 상관없이 단계 수가 동일하다.
시작과 중간, 마지막 인덱스읽기는 배열의 크기와 상관 없이 모두 딱 한 단계면 충분하다.
배열의 길이를 찾고 그 길이를 2로 나누는 것 역시 한 단계다.
단계 수가 상수이므로, 즉 N에 관계 없이 일정하므로 이 알고리즘은 O(1)이다.
의류 상표
의류 업체가 쓸 소프트웨어를 작성 중이라고 가정하자.
새로 생산한 의류 품목과 각 사이즈(1~5)가 들어가야 한다.
예를 들어, ["Purple Shirt", "Green Shirt"]라는 배열을 받았다면 이 셔츠에 들어갈 상표 텍스트는 아래와 같다.
def mark_inventory(clothing_items):
clothing_options = []
for item in clothing_items:
for size in range(1, 6):
clothing_options.append(item + " Size: " + str(size))
return clothing_options
이 알고리즘에 중첩 루프가 들어갔다고 해서 O(N²)라고 판단하면 안된다.
바깥 루프가 N번 실행되는 동안 안쪽 루프가 5번 실행된다.
따라서 단계수는 5N이다.
빅 오 표기법은 상수를 무시하니 O(N)이다.
1 세기
이 예제는 배열들의 배열을 받는다. 이때 안쪽 배열들은 다수의 1과 0으로 이뤄진다.
함수는 배열들에 들어 있는 1의 개수를 반환한다.
예를 들어, 입력이 아래와 같을 때
1이 7개이니 함수는 7을 리턴한다.
def count_ones(outer_array):
count = 0
for inner_array in outer_array:
for number in inner_array:
if number == 1:
count += 1
return count
이 함수 또한 중첩루프가 있다고 해서 섣불리 O(N²)로 판단하면 안된다.
루프 두 개가 완전히 다른 배열을 순회하기 때문이다.
바깥 루프는 안쪽 배열을 순회하고 안쪽 배열은 실제 수를 순회한다.
결국에는 안쪽 루프가 총 수 개수 만큼만 실행된다.
따라서 N은 수의 개수다.
따라서 이 함수의 시간복잡도는 O(N)이다.
팰린드롬 검사기
팰린드롬은 앞으로 읽으나 뒤로 읽으나 똑같은 단어 혹은 구절이다.
"racecar", "kayak", "deified" 등이 팰린드롬이다.
다음은 어떤 문자열이 팰린드롬인지 판단하는 자바스크립트 함수이다.
function isPalindrome(string) {
let leftIndex = 0;
let rightIndex = string.length - 1;
while (leftIndex < string.length / 2) {
if (string[leftIndex] !== string[rightIndex]) {
return false;
}
leftIndex++;
rightIndex--;
}
return true;
}
N은 함수에 전달된 문자열의 크기다.
while루프는 문자열의 반만 순회한다.
즉, 루프가 N / 2 단계를 실행한다는 뜻이다.
빅 오는 상수를 무시하기 때문에 O(N)이다.
모든 곱 구하기
예제1
이 예제는 수 배열을 받아 모든 두 숫자 조합의 곱을 리턴하는 알고리즘이다.
예를 들어 [1, 2, 3, 4, 5]라는 배열을 전달하면 함수는 아래처럼 반환한다.
[2, 3, 4, 5, 6 ,8 ,10, 12, 15, 20]
1 x (2, 3, 4, 5) = 2, 3, 4, 5
2 x (3, 4, 5) = 6, 8, 10
3 x (4, 5) = ,12, 15
4 x 5 = 20
위 알고리즘을 자바스크립트로 구현하면 아래와 같다.
function twoNumberProducts(array) {
let products = [];
for(let i = 0; i < array.length - 1; i++) {
for(let j = i + 1; j < array.length; j++) {
products.push(array[i] * array[j]);
}
}
return products;
}
함수에 원소 수가 N개인 배열이 들어온다면
바깥 루프는 약 N번 순회한다.(실제로는 N-1)
안쪽 루프는 바깥 루프를 한 번씩 돌 때마다 단계 수는 1씩 감소한다.
원소가 5개인 배열에서 안쪽 루프는
4 + 3 + 2 + 1 번 실행된다.
이러한 바깥 루프와 안쪽 루프의 관계의 패턴은 N² / 2 단계로 계산된다.
예를 들어 N이 8이라고 가정하면
맨 윗줄은 N칸 모두 회색으로 칠해져 있다. 다음 줄은 N-1개가 회색이고, 그 다음 줄은 N-2가 회색 칸이다. 한 칸만 회색인 마지막 줄까지 이 패턴이 이어진다. 이는 N + (N - 1) + (N - 2) + (N - 3) + ... + 1 이고 이 패턴은 약 N² / 2와 비슷하다
따라서 O(N²)이다.
예제2
배열 한 개의 모든 두 수의 곱을 계산하는 대신, 한 배열의 모든 수와 다른 한 배열의 모든 수의 곱을 계산하면,
예를 들어 배열 [1, 2, 3]과 배열 [10, 100, 1000]이 있으면 곱은 아래처럼 계산된다.
[10, 100, 1000, 20, 200, 2000, 30, 300, 3000]
function twoNumberProducts(array1, array2) {
let products = [];
for(let i = 0; i < array1.length; i++) {
for(let j = 0; j < array2.length; j++) {
products.push(array1[i] * array2[j]);
}
}
return products;
}
첫 번째 배열의 원소 수가 N이고, 두 번째 배열의 원소 수가 M이면
이 때 두 가지 시나리오를 세울 수 있다.
N = M
N != M
예를 들어 첫 번째 시나리오대로 N=M이어서 두 배열 5의 크기를 가지는 배열이라고 가정하면
5 x 5 = 25 즉, O(N²)이다.
두 번째 시나리오대로 N != M이면, N=9, M= 1이면
9 x 1 = 9 즉,대략 N단계이므로 O(N)이다.
이렇게 N과 M의 크기에 따라 달라지는 관계에선 O(NxM)으로 표기한다.
O(NxM)은 O(N)과 O(N²)의 사이 정도로 이해할 수 있다.
암호 크래커
소문자 a~z까지의 알파벳으로 이루어진 n자리 암호문을 브루트 포스 알고리즘으로 푼다면 아래와 같다.
위 함수는 n이 3이라면 aaa와 zzz범위 내 가능한 모든 문자열을 순회한다.
n이 4라면 아래와 같이 순회를 한다.
이는 n=1이면 26번 루프를 돌고, n=2면 26²번 루프를 돈다.
즉, 26ⁿ번 루프를 돈다.
따라서 빅 오 표기법으로는 O(26ⁿ)로 표기한다.
O(2ⁿ)는 O(N³)보다 어느 시점부턴 훨씬 느리다.
O(26ⁿ)은 O(2ⁿ)보다 훨씬 느리다.
O(2ⁿ)은 O(log N)의 반대이다. O(log N)는 데이터가 두 배 늘어날 때 단계수가 1늘어난다. O(2ⁿ)는 데이터가 1늘어날 때 단계수가 두 배 늘어난다.
