# 알고리즘 복잡도 표현 방법

# 1. 알고리즘 복잡도 계산이 필요한 이유
# - 하나의 문제를 푸는 알고리즘은 다양할 수 있음

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

# 2. 알고리즘 복잡도 계산 항목
# 1) 시간 복잡도 : 알고리즘 실행 속도(시간에 따른 속도)
# 2) 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈(메모리 사용량)
# 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 한다.

# 알고리즘 시간 복잡도의 주요 요소
# - 반복문이 지배한다

# 마찬가지로 프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문이다.
# 입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배

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

# <Big-O 표기법>
# 입력 n에 따라 결정되는 시간 복잡도 함수
# O(1), O(logn), O(n) 등 표현
# 입력 n의 크기에 따라 가하급수적으로 시간 복잡도가 늘어날 수 있음
# 단순하게 입력n에 따라 몇번 실행 되는지를 계산
# 표현식에 가장 큰 영향을 미치는 n(입력)의 단위로 표기한다
# n1이 1이든 100이든, 1000이든 10000이든 실행을 
# 무조건 2회(상수회) 실행한다 O(1)
# n에 따라 n번, n + 10번 또는 3n+10 번등 실행한다 : O(n)
# n에 따라 n제곱, n제곱+1000번 또는 100제곱-100번등 실행한다

# 2. 오메가 표기법
# - 오메가 표기법은 알고리즘 최상의 실행 시간을 표기

# 3. (세타)표기법
# - 오메가 표기법은 알고리즘 평균 실행 시간을 표기

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




