점근 표기법(+배열에서 특정 요소 찾기)

점근 표기법이란?

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

(아 이 알고리즘 좋던데? 이렇게 말하는 게 아니라 점근 표기법을 사용해서 얼마나 효율적인 지 얼마나 비효율적인 지에 대해서 평가를 쉽게 할 수 있는 방법이다.)

 

점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 지금까지 이 함수는 N 정도의 시간과 공간이 걸리겠구나 하면서 분석 했던 게 점근 표기법의 일종이라고 할 수 있다.

 

점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있습니다.

 

빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지, 빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기합니다.

 

알고리즘은 입력값에 따라서 성능이 많이 달라 질 수 있습니다.

 

예를 들어

빅오 표기법으로 표시하면 O(N)

빅 오메가 표기법으로 표시하면 Ω(1)의 시간복잡도를 가진 알고리즘이다!

라고 표현할 수 있습니다.

---

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

 

문제 설명

아래 배열 내에 특정 숫자가 존재한다면 True, 존재하지 않다면 False 를 반환하시오.

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

 

의사코드(수도코드)

- 배열 안에서 요소를 빼온다.

- if문을 사용해서 배열 안의 요소와 특정 숫자가 같으면 True를 반환, 다르면 False를 반환한다.

 

문제 풀이

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

def is_number_exist(number, array):

    # 배열 내에 특정 숫자가 존재한다면 True, 존재하지 않다면 False를 반환하는 문제
    for num in array: # array의 길이만큼 아래 연산이 실행
        if num != number: # 비교 연산 1번 실행
            return False
        else:
            return True

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

 

선생님의 문제 풀이

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

def is_number_exist(number, array):

    for element in array: // array의 길이만큼 아래 연산이 실행
        if number == element: // 비교 연산 1번 실행
            return True

    return False


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

N * 1 = N이기 때문에 총 N만큼의 시간 복잡도가 걸렸다고 할 수 있다.

운이 좋으면 1번만 연산해도 원하는 값을 찾을 수 있고 운이 나쁘면 array의 길이만큼 연산을 해야 원하는 값을 찾을 수 있다. 이처럼 알고리즘은 성능이 항상 같은 게 아니라 입력값에 따라서(입력값의 분포에 따라서) 성능이 변화 할 수 있다.

 

이를 표로 나타내면 다음과 같이 나타낼 수 있다.

즉 위의 경우에는

빅오 표기법으로 표시하면 O(N),

빅 오메가 표기법으로 표시하면 Ω(1) 의 시간복잡도를 가진 알고리즘이다! 라고 말할 수 있습니다.

 

1주차에서 기억 해야 할 핵심!!

1. 입력값에 비례해서 얼마나 늘어날 지 파악하자 1 ? N ? N^2 ?

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

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