[Python] 시간복잡도-알고리즘 복잡도 표현 방법

알고리즘 복잡도 표현 방법

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

하나의 문제를 푸는 알고리즘은 다양할 수 있는데, 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해 복잡도를 정의하고 계산함

 

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

• 시간 복잡도 : 알고리즘 실행 속도
• 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

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

 

알고리즘 시간 복잡도의 주요 요소는 반복문입니다. 입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배합니다.

 

3) 알고리즘 성능 표기법

-Big O(빅-오) 표기법 : O(N)

• 알고리즘 최악의 실행 시간을 표기
• 가장 많이/일반적으로 사용함
• 아무리 최악의 상황이라도 이 정도의 성능은 보장한다는 의미

-Ω(오메가) 표기법 : Ω(N)

• 오메가 표기법은 알고리즘 최상의 실행 시간을 표기

-Θ(세타) 표기법 : Θ(N)

• 세타 표기법은 알고리즘 평균 실행 시간을 표기

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

 

4) Big O(빅-오) 표기법

-O(입력)

• 입력 n에 따라 결정되는 시간 복잡도 함수
• O(1), O(logn), O(n), O(nlogn), O(n^2), O(2^n), O(n!) 등으로 표기함
• 입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
  • O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)
  • logn의 베이스는 2

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

• 표현식에 가장 큰 영향을 미치는 n의 단위로 표기
• n이 1, 100, 1000, 10000일 때 실행을 각각
  • O(1) : 무조건 2회(상수회) 실행

    • if n > 10:
      	print(n)

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

    • for index in range(n):
      	print(index)

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

  • O(n^2) : n에 따라, n^2번, n^2+1000번, 100n^2-100번 등 실행

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

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

 

5) 실제 알고리즘을 예로 각 알고리즘의 시간 복잡도와 빅 오 표기법 알아보기

알고리즘1 : 1부터 n까지의 합을 구하는 알고리즘1

 

<알고리즘 설명>

-합을 기록할 변수를 만들고 0을 저장

-n을 1부터 1씩 증가하면서 반복

-반복문 안에서 합을 기록할 변수에 1씩 증가된 값을 더함

-반복이 끝나면 합을 출력

 

<소스 코드>

def sum_all(n):
	total = 0
    for num in range(1, n + 1):
    	total += num
    return total

 

<시간 복잡도 구하기>

-입력 n에 따라 덧셈을 n번 해야 함(반복문 1)

-시간 복잡도 : n, 빅 오 표기법 : O(n)

 

알고리즘2 : 1부터 n까지의 합을 구하는 알고리즘2

 

<알고리즘 설명>

-n(n + 1) / 2

 

<소스 코드>

def sum_all(n):
	return int(n * (n + 1) / 2)

 

<시간 복잡도 구하기>

-입력 n이 어떻든 간에 곱셈/덧셈/나눗셈을 하면 됨(반복문이 없음)

-시간 복잡도 : 1, 빅 오 표기법 : O(1)

 

 

출처 : 제로베이스