[필수] 알고리즘 성능 평가 (시간복잡도, 공간복잡도)

1. 알고리즘 성능이란,

같은 문제라도 접근하는 알고리즘은 다양하다.

어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산하게 되었다.

 

 

2. 알고리즘 복잡도 계산 항목

   (1) 시간 복잡도: 알고리즘 실행 속도

   (2) 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

* 가장 중요한 시간 복잡도를 이해하고 스스로 계산할 줄 알아야 한다!

 

 

3. 시간복잡도 계산하는 방법

반복문(for. while 등)을 기준으로 계산한다.

그 이유는, 입력 개수가 몇개인지에 따라 반복문 내부 코드가 반복되기 때문이다.

 

 

4. 알고리즘 성능 표기법

    (1) Big O(빅오) 표기법: 최악의 실행시간을 표기하는 방법

        (최악의 상황이라도 이정도 성능은 보장한다는 의미)

    (2) 오메가 표기법: 최상의 실행시간을 표기하는 방법

    (3) 세타 표기법: 평균 실행시간을 표기하는 방법

 

 

5. 대문자 O 표기법

O(1), O(𝑙𝑜𝑔𝑛), O(n), O(n𝑙𝑜𝑔𝑛), O(𝑛2), O(2𝑛), O(n!)등으로 표기

 

* 여기서 주의할 점,

n이 무한대로 발산한다고 가정하면 상수(1,2,3...)는 0에 가까울만큼 영향력이 줄어든다.

    >> 시간 복잡도 함수가 n+1이나 n+100000이어도 모두 O(n)이라고 표현한다.

    >> 시간 복잡도 함수가 2𝑛2 + 3n 이라면 O(𝑛2)

 

• 무조건 2회(상수회) 실행한다: O(1)

        if n > 10:
             print(n)

• n에 따라, n번, n + 10 번, 또는 3n + 10 번등 실행한다: O(n)

        variable = 1
        for num in range(3):
            for index in range(n):
                 print(index)

• n에 따라, 𝑛2번, 𝑛2 + 1000 번, 100𝑛2 - 100, 또는 300𝑛2 + 1번등 실행한다: O(𝑛2)

        variable = 1
        for i in range(300):
            for num in range(n):
                for index in range(n):
                     print(index)

입력의 크기에 따라 시간복잡도가 얼마나 늘어나는지 보여주는 그래프