[algorithm] Big O 표기법

1. Big O 표기법이란?

 

• 정의: Big O 표기법은 컴퓨터 과학에서 알고리즘의 실행 시간 복잡도 또는 최악의 경우 시나리오를 입력 크기에 따라 설명하는 수학적 표기법입니다.

 

2. Big O 표기법을 사용하는 이유

 

1. 알고리즘 효율성 비교: 동일한 문제를 해결하기 위해 여러 알고리즘의 효율성을 비교합니다.

2. 알고리즘 동작 예측: 입력 크기 증가에 따른 알고리즘의 성능 변화를 예측합니다.

3. 코드 최적화 지표: 성능을 최적화하는 데 참고할 수 있는 지표로 사용됩니다.

4. 자원 관리 지표: 메모리 사용, CPU 성능 등을 고려한 자원 관리에 유용합니다.

5. 효율적인 문제 접근법 제시: 효율적인 해결 방법을 찾는 데 도움을 줍니다.

 

3. 직접 시간을 측정해서 코드 성능 평가의 어려움

 

• 실시간 측정의 어려움: 코드의 실행 시간을 직접 재는 것은 비효율적입니다. 실행 시간이 1시간, 4시간으로 다르게 나올 경우 실제 성능을 파악하기 어렵습니다.

 

4. 좋은 알고리즘이란?

 

1. 빠른 알고리즘: 실행 속도가 빠릅니다.

2. 메모리를 적게 사용하는 알고리즘: 메모리 효율이 높습니다.

3. 가독성이 좋은 알고리즘: 유지보수가 쉽고 이해하기 쉬운 코드입니다.

 

5. Big O 표기법을 위한 연산 개수 세기

 

1. 연산의 총 개수 파악: 컴퓨터가 수행하는 연산의 총 개수를 세어 복잡도를 평가합니다.

2. 반복문 분석: 예를 들어 반복문이 있는 함수는 최소 n번의 연산을 수행합니다.

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

 

 

6. Big O 표기법 구하는 법

 

1) 시간 복잡도

 

• 작은 연산은 무시: 세부적인 작은 연산보다 전체적인 추세가 중요합니다.

• 기본 규칙:

• 단순 연산, 변수 할당 ⇒ O(1)

• 루프 ⇒ O(n)

• 중첩 루프 ⇒ O(n^2)

• 예시 변환:

• O(2n) ⇒ O(n)

• O(500) ⇒ O(1)

• O(13n^2) ⇒ O(n^2)

• O(n + 10) ⇒ O(n)

• O(1000n + 50) ⇒ O(n)

• O(n^2 + 5n + 8) ⇒ O(n^2)

 

2) 공간 복잡도

 

• 입력에 따른 공간 사용: 입력이 커질수록 요구되는 공간도 증가합니다.

• 보조 공간 복잡도: 입력 데이터를 제외하고 알고리즘이 추가로 사용하는 공간이 중요합니다.

• 자료형별 공간 복잡도:

• boolean, numbers, undefined, null ⇒ O(1)

• 문자열, 참조형, 배열, 객체 ⇒ O(n) (여기서 n은 배열의 길이 또는 객체의 키 개수)

 

7. 시간 복잡도의 종류

• O(1): 상수 시간 복잡성으로, 알고리즘의 실행 시간이 입력 크기와 관계없이 일정하게 유지됩니다.

• O(log n): 로그 시간 복잡성으로, 알고리즘의 실행 시간이 입력 크기에 따라 로그적으로 증가합니다.

• O(n): 선형 시간 복잡성으로, 알고리즘의 실행 시간이 입력 크기에 따라 선형적으로 증가합니다.

• O(n log n): 선형 로그 시간 복잡성으로, 효율적인 정렬 알고리즘인 병합 정렬 및 힙 정렬에서 일반적으로 볼 수 있습니다.

• O(n^2): 제곱 시간 복잡성으로, 알고리즘의 실행 시간이 입력 크기에 따라 제곱으로 증가합니다.

종류별 : 시간 복잡도

 

참고 자료

- https://www.simplilearn.com/big-o-notation-in-data-structure-article

Big O Notation: A Complete Overview With Real-World Applications

- https://www.udemy.com/course/best-javascript-data-structures/?couponCode=PLOYALTY0923