코딩 인터뷰 완전분석 | 6. Big-O 문제 풀이

VI. Big-O

예제 1

배열을 동일한 시간대에 여러 번 읽어도 시간 복잡도엔 영향 없음

function foo(array: number[]): void {
    let sum = 0;
    let product = 1;
    for (let i: number = 0; i < array.length; i++) {
        sum += array[i];
    }
    for (let i: number = 0; i < array.length; i++) {
        product *= array[i];
        console.log(`${sum} ${product}`);
    }
}

 

 

예제 2

주어진 두 원소쌍을 모두 출력하므로 O(N^2)

 

예제 3

예제 2에서 안쪽루프가 N+1부터 시작하지만, 결과적으로  1 ~ (N-1)의 합으로 N(N-1)/2 , O(N^2)

 

예제 7

O(N) 와 같은 것

O(2N)

O(N+P), P < N/2

O(N+logN)

 

예제 9

균현 이진 탐색 트리에서 모든 노드 값을 더할 때

O(N), N : 노드 개수

 

예제 10

시간 복잡도 : O(√n)

function isPrime(n: number): boolean {
    for (let x = 2; x * x <= n; x++) {
        if (n % x === 0) {
            return false;
        }
    }
    return true;
}

// 아래 함수와 동일한 계산을 수행
function isPrime(n: number): boolean {
    for (let x = 2; x <= Math.sqrt(n); x++) {
        if (n % x === 0) {
            return false;
        }
    }
    return true;
}

 

 

예제 11

n! 구하는 경우, n부터 1 까지 반복하는 재귀함수

O(n)

 

예제 12

permutation 함수는 n!번 호출

문자열 연결을 수행할 때  O(N)시간이 소요

즉, 

permutation 호출 상한 : O(n*n!)

한 번 호출하면 O(N) 시간 걸림

총 수행시간은 O(n^2*n!) 안 넘음

 

예제 13

N번 째 피보나치 수 구하기

재귀 호출 패턴으로 O(분기^깊이)

각 호출마다 분기개 2개, 깊이 N이면 O(2^N)

 

예제 14

0 ~ n까지 피보나치 수열 전부 출력

fib(1) => 2^1번 호출

fib(2) => 2^2번 호출

...

fib(n) => 2^n번 호출

따라서 2^1 + 2^2 + ... + 2^n 은 2^(n+1)

O(2^(n+1) ) => O(2^n)

 

예제 15

피보나치 수열을 0 부터 n까지 모두 출력하지만, 이전 결과를 정수 배열에 저장(캐싱)함

캐시의 값을 찾아서 다시 저장하고 반환을 반복하는 상수 시간의 작업이 소요

즉, 상수의 일을 N번하여 O(N)

*메모이제이션: 재귀 알고리즘의 지수 시간을 최적화하는 데 많이 사용

 

예제 16

1 ~ n 의 모든 2의 n제곱 값을 출력하는 함수

1 ~ n 에서 2의 n제곱(승수) 개수는 log n 개 있으므로 수행 시간도 O(log n)