03. 알고리즘의 효율 분석

1. 시간 복잡도란

알고리즘을 선택하는 기준은 시간복잡도로 선택한다.

시간복잡도란 알고리즘의 성능을 나타내는 지표로, 입력크기에 대한 연산 횟수의 상한을 의미하며

시간복잡도는 낮으면 낮을수록 좋다

알고리즘 수행시간을 측정하는 방법에는 절대 시간을 측정하는 방법, 시간 복잡도를 측정하는 방법으로 총 두가지가 있다.

절대 시간을 측정하는 방법
말 그대로 시간을 측정하면 된다. ex) 실행결과가 나올 때까지의 시간을 측정하면된다.
하지만 이 방법은 실행하는 환경에 따라 달라질 수 있어서 코딩테스트에는 잘 사용되지 않는다
시간 복잡도를 측정하는 방법
연산 횟수와 관련이 있다. 시간 복잡도는 알고리즘이 시작한 순간부터 결괏값이 나올 때까지의 연산횟수를 나타낸다.
시간복잡도를 측정한 결과는 최선,보통,최악의 경우로 나눈다.

코딩 테스트에서 알고리즘의 성능을 측정할 때는 2가지가 중요하다

최악의 경우를 고려할 것
코딩테스트에서는 다양한 조합으로 테스트 케이스로 우리의 코드를 평가한다. 그중에는 최악의 값이 있을것이며 우리는 최악의 경우를 기준으로 시간 복잡도를 분석해야한다
알고리즘 성능은 정확한 연산 횟수가 아닌 추이를 활용
정확한 연산횟수는 필요없다. 내 알고리즘이 제한 시간 안에 수행될 수 있을지 정도를 파악하면 충분하다. 따라서 정확한 연산 횟수가 아닌 연산 횟수의 추이를 활용해서 성능을 측정한다.

ex)친구랑 10시 약속일경우 언제 도착해? 라고 물었을때 5분전쯤 도착한다고하지 1초까지 엄밀히 고민해서 하는 경우는 드뭄. 5분전쯤에는 56,57,58,59분이 있지만 5분전쯤이라고 카테고리화를 할 수 있음.

예와 마찬가지로 알고리즘의 성능을 측정할 때도 연산 횟수 추이만 알고 있어도 성능을 충분히 가늠할 수 있고 정확한 연산 횟수를 구할 때보다 더 빠르다는 장점이 있다.

충분히 큰 입력값 N에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 한다.

모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하므로 시간 복잡도는 최악의 경우를 가정하여 이야기하는것이 일반적임

왜 제일 빠른시간이 아닌 최악의 시간을 선택하는걸까?

제일 느린경우를 선택하는 이유는 프로그램의 안정성과 신뢰성 때문임.

예를 들어 은행 ATM 프로그램을 만든다고 생각했을때

function findUserAccount(accounts, targetId) {
    // 최선의 경우: 첫 번째 계좌가 내 계좌 (1초)
    // 최악의 경우: 마지막 계좌가 내 계좌 (100초)
    for(let account of accounts) {
        if(account.id === targetId) return account;
    }
}

만약 우리가 최선의 경우(1초)만 고려했다면

이 ATM은 1초만에 계좌를 찾아줍니다라고 광고를함 -> 실제로는 100초가 걸리는 경우 발생 -> 고객들 개뿍침

하지만.. 최악의 경우를 기준으로 잡는다면??

프로그램이 항상 예상 시간 안에 실행됨을 보장함

사용자에게 신뢰성 있는 서비스를 제공할 수 있음

시스템 과부화 방지

즉 최악의 경우에도 이정도 시간이면 돌아간다라고 확실히 말할 수 있음

빅오 표기법

최악의 경우에 대하여 시간 복잡도를 표현하는 방법중 가장 많이 사용하는 *점근적 표기법은 상한선을 활용하는 방법이다. 그리고 이 표기법을 빅오 표기법(big-O notation)이라고 한다.

빅오표기법은 어떤 프로그램 연산횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 계수를 지워 O(...)와 같이 표기하면 된다.

ex) f(x) = 2x² + 3x + 5 라면 시간 복잡도를 O(x²)와 같이 표기하면 된다.

수식	빅오 표기	설명
3x² + 5x + 6	O(x²)	다항함수로 구성되어 있으므로 최고차항 x²만 남는다
x + logx	O(x)	다항함수와 로그함수로 구성되어 있으므로 증가폭이 더 낮은 로그함수는 사라지고 다항함수만 남는다
2ˣ+ 10x⁵ + 5x²	O(2ˣ)	지수함수는 다항함수보다 빠르게 증가하므로 지수함수만 남는다
5x² - 6x	O(x²)	최고차항 x²만 남는다

*점근적 표기법: 어떤 함수의 증가하는 추세를 표현하는 표기법이다.

f(x) = 2x² + 3x + 5 이 함수는 어떤 알고리즘의 실행 시간을 나타낸다

O(x²)라고 할 때 어떤 상수 c가 있어서 충분히 큰 모든 x에 대해 f(x)는 c*x²이 성립한다는것이다.

60페이지 예를 보면 f(x) = 2x² + 3x + 5

x가 매우 커지면 x² 항이 제일 큰 영향을 미친다

3x나 5는 x²에 비하면 매우 작음. 따라서 함수의 시간 복잡도는 O(x²)이다.

x 가 1000일때

x² = 1,000,000

3x = 3,000

5 = 5

라고 이해하였으나... 좀 더 쉽게 풀어서 설명하자면

집에서 학교까지 가는데 달리기 10분, 신발신기 1분, 물마시기 30초가 걸린다 이것을 수식으로 쓰면

총 소요시간 10분 + 1분 + 0.5분

가장 오래 걸리는 시간 -> 달리기 10분

그래서 우리는 등교하는데 10분 걸린다고하지 1분,30초는 전체 시간에 비하면 큰 영향이 없어서 무시함

컴퓨터도 마찬가지로 f(x) = 2x² + 3x + 5에서 x가 매우커지면 x²이 너무 커져서 나머지 3x + 5는 상대적으로 매우작아진다.

그래서 우리는 이 프로그램은 x²만큼의 시간이 걸린다라고 표현한다

최고 차항만 남기고 계수를 지우는 이유

데이터(x)가 커질수록 각 그래프의 차이는 확연히 벌어진다. x값이 무한하게 커지면 그 격차는 더 심해짐

다항함수 x보다 x²이 더 빨리 증가 하고 지수함수는 다항함수보다 빨리, 로그함수는 다항함수보다 천천히 증가한다. x값이 충분히 커진다면 이 함수들의 y값의 격차는 천천히 증가하는 일부를 무시할 수 있을정도로 커질것이다.

무시하는 이유는 우리가 구하려는 것은 상한의 정확한 값이 아닌 이 정도 될 것이다를 파악하는 추이이기 떄문임.

따라서 알고리즘 성능을 가늠하기 위해서는 가장 의미있는 상한을 구하는게 중요하다.

함수의 증가율(성장률)을 큰 순서대로 나열한것
1	y = x!	팩토리얼 함수
2	y = 2ˣ	지수함수
3	y = x²	다항함수
4	y = xlogx	로그함수와 다항함수의 조합
5	y = x	다항함수
6	y = logx	로그함수
7	y = 1	상수

우선 순위에 따라 최고 차항을 제거하면 된다.

y값의 증가율에 따라 지수함수, 다항함수, 로그함수 순으로 최고차항이라고 생각하고 최고차항이 아닌 함수를 지우면 된다

시간 복잡도는 반대로 해석하면 됨
1	O(1)	상수 시간 (가장 빠름)
2	O(log N)	로그 시간
3	O(N)	선형 시간
4	O(N log N)	선형 로그 시간
5	O(N²)	제곱 시간
6	O(2ⁿ)	지수 시간
7	O(n!)	팩토리얼 함수

그래프가 낮을 수록 = 성능이 좋다

그래프가 높을 수록 = 성능이 나쁘다

라고 이해하면 됨 팩토리얼 포함 그래프를 봤을때 O(n!) 시간복잡도를 가진 알고리즘이 일반적으로 가장 성능이 좋지않은 경우이다.

시간복잡도를 코딩테스트에 활용하기

시간복잡도	최대 연산 횟수
O(N!)	10
O(2ᴺ)	20~25
O(N³)	200~300
O(N²)	3,000 ~ 5,000
O(NlogN)	100만
O(N)	1,000만 ~ 2,000만
O(logN)	10억

대략 데이터가 1,000만개 정도면 O(N)을 사용해야하는구나 정도로 감을 익힐것

N이 500 이하: O(N³) 가능
N이 2,000 이하: O(N²) 가능
N이 100,000 이하: O(NlogN) 가능
N이 10,000,000 이하: O(N) 가능

// 입력 크기가 1000만(10,000,000)일 때:

// O(N) - 가능 (1초 이내)
function linearTime(arr) {
    for(let i = 0; i < arr.length; i++) {
        // 뭔가를 한다
    }
}

// O(N²) - 불가능! (너무 오래 걸림)
function quadraticTime(arr) {
    for(let i = 0; i < arr.length; i++) {
        for(let j = 0; j < arr.length; j++) {
            // 뭔가를 한다
        }
    }
}

const sizes = [100, 1000, 10000, 100000];

sizes.forEach(n => {
    console.log(`입력 크기(N)가 ${n}일 때:`);
    console.log(`O(N)   연산 수: ${n}`);
    console.log(`O(N²)  연산 수: ${n * n}`);
    console.log(`O(NlogN) 연산 수: ${Math.floor(n * Math.log2(n))}`);
    console.log('------------------------');
});

// 1000만일 때는 별도로 계산
const tenMillion = 10000000;
console.log(`입력 크기(N)가 1000만일 때:`);
console.log(`O(N)     연산 수: ${tenMillion}`);
console.log(`O(NlogN) 연산 수: ${Math.floor(tenMillion * Math.log2(tenMillion))}`);

입력 크기(N)가 100일 때:
O(N)   연산 수: 100
O(N²)  연산 수: 10000
O(NlogN) 연산 수: 664
------------------------
입력 크기(N)가 1000일 때:
O(N)   연산 수: 1000
O(N²)  연산 수: 1000000
O(NlogN) 연산 수: 9965
------------------------
입력 크기(N)가 10000일 때:
O(N)   연산 수: 10000
O(N²)  연산 수: 100000000
O(NlogN) 연산 수: 132877
------------------------
입력 크기(N)가 100000일 때:
O(N)   연산 수: 100000
O(N²)  연산 수: 10000000000
O(NlogN) 연산 수: 1660964
------------------------
입력 크기(N)가 1000만일 때:
O(N)     연산 수: 10000000
O(NlogN) 연산 수: 232534966

N이 작을 때는 O(N²)도 괜찮지만
N이 10만만 되어도 O(N²)는 100억번 연산
반면 O(N)은 10만번이면 충분

실제로 문제 풀 때 이렇게 체크하기

입력 크기를 확인한다
내가 작성한 코드가 몇 번 반복되는지 본다
1. 중첩 반복문이 2개면 O(N²)
2. 반복문이 1개면 O(N)
입력 크기에 맞는 시간복잡도인지 확인

책 예시(64페이지)에서 배열 검색하는것처럼 하나하나 짚어가며 찾는방식은 O(N)시간 복잡도를 가지고

이런 방식을 선형 검색 또는 순차 검색이라고 한다.

배열이 정렬되어 있다면 이진검색이라는 O(logN) 방식을 쓸 수 있다.

일반 배열 검색 (정렬 안됨) -> O(N)
정렬된 배열에서 이진 검색 -> O(log N)

정렬되지 않은 데이터는 array.find(),Array.indexOf 같은 O(N) 메서드를 사용하고

정렬된 데이터는 이진 검색을 사용한다

아주 자주 검색해야 하는 데이터는 객체(Object)나 Map을 사용해 O(1)로 만들기도 한다.

외우면 좋은 패턴들

1. O(N): 하나하나 다 봐야 하는 경우

배열 전체 순회할 때
배열에서 뭔가 찾을 때
for문 하나 쓸 때

2. O(N²): 이중 for문 쓸 때

2중 반복문
배열 속의 모든 원소를 또 다른 모든 원소와 비교할 때

3. O(logN): 반씩 잘라서 볼 때

이진 탐색
정렬된 데이터에서 뭔가 찾을 때

4. O(1): 바로 접근할 수 있을 때

배열의 특정 위치 접근
객체의 속성 접근

시간 복잡도 계산해보기

1. 문제 정의

2. 연산 횟수 측정

3. 시간 복잡도를 분석

별찍기 문제

67페이지 예

f(N) = 1 + 2 ... + N = N(N+1)/2

빅오 표기법으로는 f(N²)라고 할 수 있음

뭔소린겨 싶은데

N=3일 때: 1+2+3 = 6
N=4일 때: 1+2+3+4 = 10
N=5일 때: 1+2+3+4+5 = 15

n의 크기가 커질 수록 연산횟수가 빠르게 커진다

이걸 N(N+1)/2 공식에 넣어보면 똑같은 결과가 나온다.

// 1부터 N까지의 합을 직접 계산해보기
function calculateSum(N) {
    let sum = 0;
    for(let i = 1; i <= N; i++) {
        sum += i;
    }
    return sum;
}

// N(N+1)/2 공식으로 계산해보기
function calculateFormula(N) {
    return (N * (N + 1)) / 2;
}

// 둘 다 계산해서 비교해보기
for(let N = 1; N <= 5; N++) {
    console.log(`N이 ${N}일 때:`);
    console.log(`직접 계산한 합: ${calculateSum(N)}`);
    console.log(`공식으로 계산: ${calculateFormula(N)}`);
    console.log('------------------------');
}

N이 1일 때:
직접 계산한 합: 1
공식으로 계산: 1
------------------------
N이 2일 때:
직접 계산한 합: 3
공식으로 계산: 3
------------------------
N이 3일 때:
직접 계산한 합: 6
공식으로 계산: 6
------------------------
N이 4일 때:
직접 계산한 합: 10
공식으로 계산: 10
------------------------
N이 5일 때:
직접 계산한 합: 15
공식으로 계산: 15
------------------------

값이 O(N²)인 이유

function compareValues(N) {
    let sum = (N * (N + 1)) / 2;  // 우리의 원래 공식
    let squared = N * N;          // N²
    
    console.log(`N이 ${N}일 때:`);
    console.log(`원래 공식 결과: ${sum}`);
    console.log(`N² 결과: ${squared}`);
    console.log(`비율: ${sum / squared}`);
    console.log('------------------------');
}

// 큰 숫자들로 테스트
compareValues(10);
compareValues(100);
compareValues(1000);

N이 커질수록 N(N+1)/2는 N²의 약 1/2배에 가까워짐

즉, 결국 N이 매우 커지면 N²과 비슷한 비율로 증가한다는 뜻

그래서 O(N²)이라고 한다.

박테리아 수명문제

처음에 박테리아가 16마리

매년 절반으로 줄어듦

몇 년 후에 1마리 미만이 되나?

1년차: 16 × (1/2) = 8마리
2년차: 8 × (1/2) = 4마리
3년차: 4 × (1/2) = 2마리
4년차: 2 × (1/2) = 1마리
5년차: 1 × (1/2) = 0.5마리 (이때 박테리아 소멸!)

수학적으로 표현하면

처음: N = 16
1년 후: N × (1/2)
2년 후: N × (1/2)²
3년 후: N × (1/2)³
...
Y년 후: N × (1/2)ʸ

우리가 찾는것은

N × (1/2)ʸ < 1 이 되는 가장 작은 Y
16 × (1/2)ʸ < 1

이걸 풀면

16 × (1/2)⁵ = 0.5 < 1

따라서 5년이다.

왜 O(logN)이냐면

매번 반으로 줄어들고 반으로 줄어드는 횟수는 log²N과 같음

16의 경우 log²16 =4에 가까운 숫자가 나옴

입력값 N이 아무리 커도 반으로 계속 나누면 빨리 1에 도달할 수 있다. 이런 특성을 가진 알고리즘을 O(logN)이라고함

대표적인 O(logN)패턴

1. 숫자가 계속 반으로 줄어드는 경우

박테리아가 바능로 줄어드는 경우
이진 탐색처럼 범위를 반으로 줄여가는 경우

2. 숫자가 계속 반으로 나눠지는 경우

let n = 16;
while (n > 1) {
    n = n / 2;  // 16 -> 8 -> 4 -> 2 -> 1
}

반대로 하나씩 줄어들면 O(N)

반으로 줄어들면 O(log N)

으로 구분할것

코딩 테스트 합격자 되기 - 자바스크립트 편을 참고하여 작성했습니다

코딩공부