[Python] 시간 복잡도

시간 복잡도

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

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

• 정수의 절대값 구하기
  • 방법1 : 정수 값을 제곱한 값에 다시 루트 씌우기
  • 방법2 : 정수가 음수인지 확인해서, 음수일 때만 -1을 곱하기

 

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

• 시간 복잡도 : 알고리즘 실행 속도
• 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈
• Big O (빅-오) 표기법 : O(N)
  • 알고리즘 최악의 실행 시간을 표기
  • 가장 많이/일반적으로 사용
  • 아무리 최악의 상황이라도, 이 정도의 성능은 보장한다는 의미
• \(\Omega\)(오메가) 표기법 : \(\Omega\)(N)
• \(\Theta\)(세타) 표기법 : \(\Theta\)(N)

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

 

3. 대문자 O 표기법

• 빅 오 표기법
• O(입력)
  • 입력 n에 따라 결정되는 시간 복잡도 함수
  • \(O(1), O(\log n), O(n), O(n\log n), O(n^2), O(2^n), O(n!)\) 등으로 표기함
  • 입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어난다.
    • \(O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)<O(n!)\)
• 단순하게 입력 n에 따라 몇 번 실행이 되는 지를 계산하면 된다.
  • 표현식에 가장 큰 영향을 미치는 n의 단위로 표기
  • n이 1이든 100이든 10000이든 실행을
    • 무조건 2회(상수) 실행한다. : \(O(1)\)
    • n에 따라 n번 n+10번 또는 3n+10번 실행한다. : \(O(n)\)
    • n에 따라 \(n^2\)번 \(n^2+1000\)번 등을 실행한다 : \(O(n^2)\)

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

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