[Algorithm] 알고리즘 복잡도 표현방법

알고리즘 복잡도 표현방법

1. 알고리즘 복잡도 계산이 필요한 이유

하나의 문제를 푸는 알고리즘은 다양할 수 있음.

다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함

2. 알고리즘 복잡도 계산항목

1. 시간 복잡도 : 알고리즘 실행 속도

2. 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함

알고리즘 시간 복잡도의 주요 요소

반복문이 대부분.

알고리즘 성능 표기법

• Big O (빅-오) 표기법: O(N)
  • 알고리즘 최악의 실행 시간을 표기
  • 가장 많이, 일반적으로 사용
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미
• Ω (오메가) 표기법: Ω(N)
  • 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
• Θ (세타) 표기법: Θ(N)
  • 오메가 표기법은 알고리즘 평균 실행 시간을 표기

시간 복잡도 계산은 반복문이 핵심 요소임. 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 된다.

3. 대문자 O 표기법

• 빅-오 표기법, Big-O 표기법이라고 함
• O(입력)
  • 입력 n 에 따라 결정되는 시간 복잡도 함수
  • O(1), O(𝑙𝑜𝑔𝑛logn), O(n), O(n𝑙𝑜𝑔𝑛logn), O(𝑛2n2), O(2𝑛2n), O(n!)등으로 표기함

• 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 됨

  • 표현식에 가장 큰 영향을 미치는 n의 단위로 표기

  • n이 1이든 100이든, 1000이든 실행을

    • 무조건 2회(상수회) 실행한다: O(1)

    if n > 10:
    	print(n)
    

    • n에 따라 n번, n+10번, 3n+10번등 실행한다: O(n)

    variable = 1
    for num in range(3):
    	for index in range(n):
    		print(index)
    

    • n에 따라, $n^2$번, $n^2$ + 1000 번, 100$n^2$ - 100, 또는 300$n^2$ + 1번등 실행한다: O($n^2$)

    variable = 1
    for i in range(300):
    	for num in range(n):
    		for index in range(n):
    			print(index)
    

    출처: http://www.fun-coding.org/00_Images/bigo.png

    • 빅 오 입력값 표기 방법
      • 예:
        • 만약 시간 복잡도 함수가 $2n^2$ + 3n 이라면
          • 가장 높은 차수는 2$n^2$
          • 상수는 실제 큰 영향 없음
          • 결국 빅 오 표기법으로는 O($n^2$)

이후 자료구조, 알고리즘부터는 빅 오 표기법으로 성능을 계산해보면서, 빅 오 표기법과 계산방법에 익숙해지는게 좋다.