점근 표기법

[점근 표기법이란?]

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

어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법

지금까지 "~시간과 공간이 걸리겠구나" 하면서 따졌던 것들이 점근표기법의 일종임

 

[점근 표기법의 종류]

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

   최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지에 대해 표기

   표기 방법 예시: O(N)

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

   최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지에 대해 표기

   표기 방법 예시: Ω(1)

---

[배열에서 특정 요소 찾기]

다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내에 특정 숫자가 존재한다면 True, 존재하지 않다면 False를 반환하시오.

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

방법)

배열을 돌면서 배열의 원소가 찾고자하는 숫자와 같은지 비교

만약 같다면 True를 반환하고, 끝까지 없다면 False를 반환

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


def is_number_exist(number, array):
    for element in array:       #array의 길이 만큼 연산 실행
        if element == array:    #비교 연산 1번 실행
            return True
        
    return False


result = is_number_exist(3, input)
print(result)

위의 함수의 시간복잡도는 N * 1만큼 가짐

 

위의 배열 안에서 3을 찾는다면 

첫번째 배열과 비교하는 순간 함수가 끝나면서 True를 반환하게 됨

운이 정말 좋게 비교하려는 숫자가 첫번째에 있으면 1만큼의 연산을 한 뒤 결과를 알 수 있음

 

반대로 위의 배열 안에서 4를 찾는다면

각 요소와 일일이 다 비교하고 마지막 요소를 비교하는 순간 True를 반환하게 됨

운이 안좋게 비교하려는 숫자가 가장 마지막에 있으면 N만큼의 연산을 한 뒤 결과를 알 수 있음

 

알고리즘의 성능은 항상 동일한 것이 아니라 입력값에 따라 달라질 수 있음!!

위 함수의 경우에는 

빅오 표기법: O(N)

빅 오메가 표기법: Ω(1) 

의 시간 복잡도를 가진 알고리즘이다

라고 말할 수 있음

 

지금까지 최악의 경우. 빅오 표기법으로만 구해온건데

알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석함!

대부분의 입력값이 최선의 경우일 가능성을 정말 적은 뿐더러, 우리는 최악의 경우를 대비해야하기 때문임

---

이것만 기억하면 됨

1. 입력값에 비례해서 얼마나 늘어날 지 파악해보자

2. 공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자

3. 최악의 경우에 시간이 얼마나 소요될 지(빅오 표기법)에 대해 고민하자