[Python] 알고리즘 기초: 시간 복잡도

점근 표기법의 두 가지 종류, O(N), Ω(1)와

시간 복잡도의 개념에 대해 이해해 봅니다.

---

1. 빅오(Big-O) 표기법

2. 빅오메가(Big-Ω) 표기법

3. 시간 복잡도

   - 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘!

---

 

 

• 점근 표기법이란?

 → 알고리즘 "효율성"을 평가하는 방법  = 알고리즘의 성능을 수학적으로 표기

 

 

1. 빅오(Big-O) 표기법 : O(N)

 

최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인가

Q. 다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내에 특정 숫자가 존재한다면 True, 존재하지 않다면 False 를 반환하는 프로그램을 작성하세요.

arr = [3, 5, 6, 1, 2, 4]

is_number_exist(3, arr) # True
is_number_exist(120, arr) # False

 

▼ solution

def is_number_exist(num, arr):
    for el in arr:
        if num == el:
            return True
    return False

 

 

★ 이 함수의 시간 복잡도는 얼마나 걸릴까?

    for el in arr:     # array 의 길이만큼 아래 연산이 실행
        if num == el:  # 비교 연산 1번 실행 
            return True
    return False

 

 

위에서 연산된 것들을 더해보면, 이렇게 총 N * 1의 시간 복잡도를 가진다는 걸 볼 수 있다.

그런데 여기서, 모든 경우에 N 만큼의 시간이 걸릴까요?

 

input = [4, 5, 6, 1, 2, 3] 이라는 입력값에 대해서 3을 찾으면 어떻게 될까요? 마지막 원소 끝까지 찾다가 겨우 마지막에 3을 찾아 결괏값을 반환하게 됩니다. 즉, 운이 좋지 않으면 input의 길이(N) 만큼 연산 이후에 답을 찾을 수 있다.  →  O(N) (빅오)

 

---

 

2. 빅오메가(Big-Ω) 표기법 : Ω(1)

 

최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인가

 

위의 예시에서,  input = [3, 5, 6, 1, 2, 4] 이라는 입력값에 대해서 3을 찾으면, 첫 번째 원소를 비교하는 순간!! 바로 결괏값을 반환하게 됩니다. 즉, 운이 좋으면 1번의 연산 이후에 답을 찾을 수 있다. →  Ω(1) (빅오메가)

 

 

※ 알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석한다.

   대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐더러, 언제나 최악의 경우를 대비해야 하기 때문이다.

 

 

---

 

3. 시간 복잡도

 

시간 복잡도란, 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계

예) 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것