# 2. 알고리즘 복잡도(Algorithm Complexity)

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

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

예를들어 정수의 절대값을 구하는 경우를 보자.

1, -1 => 1

방법1

정수값을 제곱한 후에 루트를 씌우기

방법2

정수가 음수인지 확인한후, 음수일 때만 -1을 곱하기

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

이 두가지 복잡도 계산 항목중 가장 중요한 것은 시간 복잡도이다. 시간 복잡도를 꼭 이해하고 계산할 수 있어야 한다.

시간 복잡도의 가장 중요한 요소는 반복문이다.

자동차로 서울에서 부산을 가기 위한 항목을 다음과 같이 나누어 보았을 때, 총 시간에 가장 영향을 많이 미칠 것 같은 요소를 생각해보자.

이 중에서 가장 시간에 영향을 많이 주는 교소는 5번 서울에서 부산가기이다. 이처럼 알고리즘에서도 시간에 가장 많이 영향을 주는 요소가 있는데 그것이 바로 반복문이다.

입력의 크기가 커지면 커질수록 반목문이 알고리즘의 수행 시간을 지배한다.

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

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

빅-오 표기법, Big-O 표기법이라고 부름
O(입력)
- 입력 n에 따라서 결정되는 시간 복잡도 함수이다.
O(1) < O() < O(n) < O(n) < O() < O() < O(n!) - 참고: log n 의 베이스는 2 -
- 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 됩니다.
  - 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기합니다.

아래는 O(1), O(n), O()의 시간복잡도 함수 예시이다.

if n > 10:
	print(n)

variable = 1
for num in range(3):
    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)

Time Complexity

빅-오 입력값 표기 방법 예시
- 만약 시간 복잡도 함수가 이라면, 가장 높은 차수는 이다. 그리고 상수는 실제 큰 영향을 주지 않기 때문에, 결국에 빅-오 표기법으로는 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)

위와 같이 같은 문제에 대해서도 알고리즘을 작성하는 방법에 따라서 성능차이가 다르게 나온다.

여기서는 시간 복잡도를 통해서 성능 차이를 계산해보았다.