[알고리즘의 성능 표현 방법] 시간 복잡도와 공간 복잡도 그리고 빅오 표기법

Chap1. 코딩 게임 첫 걸음 떼기

1-4. 알고리즘의 성능은 어떻게 표현할까?

• 알고리즘의 성능은 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 표현한다.

  • 시간 복잡도(Time Complexity): 시간 복잡도는 입력 값의 개수와 알고리즘의 처리 시간과의 상관관계를 표현한 말이다. 입력 데이터의 양이 많아짐에 따라 처리 속도가 어떻게 변하는지를 수학의 기호를 빌려 표현하는 방식이다.

  • "쉽게 생각하면 수학의 방정식을 떠올리면 된다."

  • x축을 입력 값의 개수로 놓고 y축을 처리 시간으로 봤을 때, x가 증가함에 따라 y가 어떻게 변화하는 지를 표현하는 것이다.

  • e.g x와 y가 일정한 비율로 증가한다면 선형(linear)시간 복잡도를 가진다고 표현한다.

    지수와 로그의 형태로 증가한다면 각각 지수형, 로그형 시간 복잡도를 가지고 있다고 표현한다.

  • 공간 복잡도(Space Complexity)도 기본적으로는 시간 복잡도와 동일하다.

  • 다만 처리 시간 대신 메모리 사용량의 변화를 비교하는 것만 다를 뿐이다.

  Example

  • 어떤 탐색 알고리즘의 입력 데이터 개수가 100개에서 1000개로 증가할 때 탐색 시간이 선형적으로 증가한다면 이 알고리즘은 '선형 시간 복잡도'를 가지고 있다고 얘기한다.
  • 입력데이터가 100개에서 1000개로 증가하더라도 처리 시간에 변화가 없다면 이 알고리즘은 상수(constant) 시간 복잡도를 가지고 있다고 한다.
  • 최근의 알고리즘은 '처리 속도'에 중점을 두기 때문에 별도의 언급이 없는 한 이 책에서 알고리즘의 성능은 시간 복잡도를 의미한다.

• 알고리즘의 성능은 빅오(big-O)표기법으로 표현한다.

• 빅오 표기법은 O(n)표기법으로 불리기도 한다.

• 이 알고리즘은 최악의 상황에서도 이 성능 이상을 보장한다는 의미이다.

• O(n) 표기법에서 괄호 안의 n은 입력 데이터의 개수를 의미한다.

• • 즉 O(n)은 입력데이터 n개에 대해 n번 처리를 수행한다는 의미이다.
  • O(n2)은 입력데이터 n개에 대해 n2번 처리를 수행한다는 의미이다.
  • O(1)은 입력데이터 n의 크기와 상관없이 항상 고정된 시간이 걸린다는 뜻이다.

    O(n) 표기법으로 성능을 표현할 때 괄호 안에는 입력 데이터의 개수 n에 대한 알고리즘의 처리시간을 표기한다.

  • O(n)을 기준으로 아래쪽에는 O(1), O(log n), O(root n)이 있다.
  • O(n)을 기준으로 위쪽에는 O(n log n), O(n**2), O(2*n), O(n!)이 있다.
  • Q. n개의 입력값이 있을 때, 시간의 복잡도 성능이 가장 안좋은 방법은 무엇일까?

시간 복잡도에 따른 성능 그래프

알고리즘 성능의 다양한 표기법

불러오는 중입니다...

• 알고리즘을 배워나가면서 하나하나 채워나가게 될 것이다.

참고자료 - 게임으로 익히는 코딩 알고리즘 || 김영기 저 || 한빛미디어

 

• color - 주황: #FFE58E
• 노랑: #FFFF8E