점근 표기법

• 알고리즘의 성능을 수학적으로 표기하는 방법(효율성)

종류

빅오(Big-O) 표기법

• 알고리즘의 최악의 성능이 나올 때 어느 정도의 연산량을 가질 것인지에 대한 것
• "$O(N)$의 시간복잡도를 가진 알고리즘이다."

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

• 최선의 성능이 나올 때 어느 정도의 연산량을 가질 것인지에 대한 것
• "$Ω(1)$의 시간복잡도를 가진 알고리즘이다."
  
  

예시

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

[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
print("정답 = True 현재 풀이 값 =", result(3,[3,5,6,1,2,4]))
print("정답 = Flase 현재 풀이 값 =", result(7,[6,6,6]))
print("정답 = True 현재 풀이 값 =", result(2,[6,9,2,7,1888]))

• N X 1 만큼의 시간복잡도를 가진다.

  그러나 모든 경우의 수에 N 만큼의 시간이 걸릴까? 입력값에 3을 넣고 한번만에 찾았으니 여러번 for문을 돌아 4를 찾는 것보다 시간이 훨씬 빠르다.

• 알고리즘의 성능은 항상 동일하지 않고 입력값에 따라 달라질 수 있다.

  입력값이	소요되는 연산량
  좋을 때	1
  안 좋을 때	N

• 표현 : 빅오 표기법으로는 $O(N)$,
  빅 오메가 표기법으로는 $Ω(1)$의 시간복잡도를 가진 알고리즘이다~
  
  

결론

• 알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석한다. 입력값이 최선의 경우일 가능성이 굉장히 적어서 항상 최악의 경우를 대비하기 때문이다.