[알고리즘] 빅 오 표기법 연습문제

다음 문제들을 빅 오 표기법으로 나타내보자.

 

 

1. 주어진 해가 윤년인지 밝히는 다음 함수의 시간 복잡도를 빅 오 표기법으로 나타내자.

 

function isLeapYear(year) {
	return (year % 100 === 0) ? (year % 400 === 0) : (year % 4 === 0);
}

 

 

해답

O(1)

함수에 전달된 년도를 N이라고 하면, 년도가 몇이든 알고리즘에 걸리는 단계 수는 일정하다.

 

 

 

 

 

 

2. 주어진 배열의 모든 수를 합하는 다음 함수의 시간 복잡도를 빅 오 표기법으로 나타내자.

 

function arraySum(array) {
	
    let sum = 0;
    
    for(let i = 0; i < array.length; i++) {
    	sum += array[i];
    }
    
    return sum;

}

 

 

해답

O(N)

배열에 원소가 N개일 때 루프는 N번 실행된다.

 

 

 

 

 

3. 다음 함수는 복리의 무서움을 보여주는 오랜 비유를 재현한 것이다.

체스판 한 칸에 쌀 한 톨을 놓는 상상을 해보자. 두 번째 칸에는 이전 칸에 놓았던 쌀 양보다 두 배 더 많은 쌀 두 톨을 놓난다. 세 번째 칸에는 쌀 네 톨을 놓는다. 네 번째 칸에는 쌀 여덟 톨을 놓고 다섯 번째 칸에는 쌀 여섯 톨을 놓는 식으로 이 과정을 반복한다.

함수는 몇 번째 칸에 일정한 수의 쌀을 놓아야 하는지 계산한다. 가령 쌀이 열여섯 톨이면 다섯 번째 칸에 놓아야 하니 함수는 5를 반환한다.

다음과 같이 구현한 이 함수의 시간 복잡도를 빅 오 표기법으로 나타내자.

 

function chessboardSpace(numberOfGrains) {

    let chessboardSpaces = 1;
    let placedGrains = 1;

    while (placeGrains < numberOfGrains) {
        placedGrains *= 2;
        chessboardSpaces += 1;
    }

    return chessboardSpaces;

}

 

 

 

해답

O(logN)

N이 두 배 늘어날 때마다 루프를 한 번 더 실행하므로 O(logN)이다.

 

 

 

 

 

4. 다음 함수는 문자열 배열을 받아 'a'로 시작하는 문자열만 포함시킨 새 배열을 반환한다. 이 함수의 시간 복잡도를 빅 오 표기법으로 나타내자.

 

function selectAStrings(array) {

    let newArray = [];

    for(let i = 0; i < array.length; i++) {
        if (array[i].startsWith("a")) {
            newArray.push(array[i]);
        }
    }

    return newArray;

}

 

 

해답

O(N)

N은 배열 내 문자열 개수이고 루프에서 N단계가 걸린다.

 

 

 

 

 

 

5. 다음 함수는 정렬된 배열의 중앙값(median)을 계산한다. 이 함수의 시간 복잡도를 빅 오 표기법으로 나타내자.

 

function median(array) {

    const middle = Math.floor(array.length / 2);

    // 배열에 짝수 개의 수가 있으면
    if (array.length % 2 === 0) {
        return (array[middle - 1] + array[middle] / 2;
    } else { // 배열에 홀수 개의 수가 있으면
        return array[middle];
    }

}

 

해답

O(1)

배열의 크기가 얼마든 알고리즘에서는 정해진 단계 수만큼만 걸린다. 알고리즘은 N이 홀수인지 짝수인지 보지만 어느 쪽이든 단계 수는 같다.

 

 

 

 

 

 

 

 

---

출처

누구나 자료구조와 알고리즘 개정 2판