자료구조(번외)- 알고리즘 복잡도 표현방법(시간복잡도)

사실 이번 코딩테스트 준비 파트를 기초부터 들어가게 된 원인이 된 녀석이다... 면접때 코딩테스트 당시 풀었던 코드에대해 시간복잡도를 여쭤보셨는데 이부분에대한 정의가 안되어있어서 대답조차 못했기때문...ㅎ... 그리어렵진 않다.

알고리즘 복잡도 표현방법

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

하나의 문제를 푸는 알고리즘은 다양함

• 정수의 절대값 구하기(1,-1)
  • 방법1:정수값을 제곱한 값에 다시 루트 씌우기
  • 방법2:정수가 음수 인지 확인해서, 음수일 때만 -1을 곱하기
  • 즉, 다양한 알고리즘 중 어느 알고리즘이 더좋은지를 분석하기 위해, 복잡도를 정의하고 계산함

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

• 시간 복잡도: 알고리즘 실행속도
• 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈
• 가장 중요한 시간 복잡도를 이해하고 계산할 수 있어야함 -> 공간복잡도는 아무래도 비중이적음

알고리즘 시간 복잡도의 주요 요소는 반복문이다. -> 입력의 크기가 커지면 커질수록 알고리즘 수행시간이 증가함

알고리즘 성능 표기법

• Big O (빅-오) 표기법: O(N)
  • 알고리즘 최악의 실행 시간
  • 가장 많이/일반적으로 사용
  • 아무리 최악의 상황이라도, 이정도의 성능을 보장한다는 의미
• Ω (오메가) 표기법: Ω(N)
  • 오메가 표기법은 알고리즘 최상의 실행 시간
• Θ (세타) 표기법: Θ(N)
  • 세타 표기법은 알고리즘 평균 실행시간을 표기
• 시간 복잡도 계산은 반복문이 핵심 요소이며, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O표기법을 중심으로 익히면 됨

3.Big-O 표기법

• 빅 오 표기법, Big-O 표기법 이라고도 부름
• O(입력값)   
• 입력 n에 따라 결정되는 시간 복잡도 함수
• O(1), O( 𝑙𝑜𝑔𝑛 ), O(n), O(n 𝑙𝑜𝑔𝑛 ), O( 𝑛2 ), O( 2𝑛 ), O(n!)등으로 표기함
• 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
• O(1) < O( 𝑙𝑜𝑔𝑛 ) < O(n) < O(n 𝑙𝑜𝑔𝑛 ) < O( 𝑛2 ) < O( 2𝑛 ) < O(n!)
• 참고: log n 의 베이스는 2 -  𝑙𝑜𝑔2𝑛 
• 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산
• 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기 -> 상수회 무시
• 예시

-무조건 2회(상수회)실행: O(1)

if n>10:
	print(n)

-n에따라, n번, n+10번 또는 10n+10번등 실행: O(n)

variable = 1
for num in range(3):
	for index in range(n):
		print(index)
# 따져보면 2n+2회이지만 결국 시간복잡도는 2n

-n에 따라, 𝑛2번 , 𝑛2+1000번,  𝑛2+1번실행한다: O(𝑛2)

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

• 성능 판단 예시: 1부터 n까지의 합을 구하는 알고리즘

# 입력값 n을 정렬하여 모두 합
def sum_all(n):
    total = 0
    for num in range(1, n + 1):
        total += num
    return total
#시간복잡도: n

# 덧셈 알고리즘 이용
def sum_all(n):
    return int(n * (n + 1) / 2)
#시간복잡도: 1

같은 문제이더라도 어떤 알고리즘을 이용하냐에 따라 시간 복잡도가 다르게 나옴 즉, 시간복잡도가 1인 2번째 알고리즘의 성능이 더욱 좋다.