3. 시간 복잡도와 공간 복잡도

1-1. 알고리즘 복잡도 계산이 필요한 이유
* 정수의 절대값을 구하는 방법
  * 방법1: 정수값을 제곱한 값에 루트 씌우기
  * 방법2: 값이 음수인지 확인하고 음수일때 -1을 구하기
> 다양한 알고리즘이 더 좋은지 분석하기 위해 복잡도를 정의하고 계산함


1-2. 알고리즘 복잡도 계산 항목
* 시간 복잡도: 알고리즘 실행 속도
* 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈


### 1-3. 알고리즘 오메가 성능 표기법
* 오메가 표기법: 알고리즘 최상의 결과를 표기
* 세타 표기법 : 알고리즘 평균 결과를 표기
* 빅오 표기법 : 최악의 실행 결과를 표기(가장 많이 사용함, 아무리 최악의 상황이라도 이 정도의 성능은 보장함을 의미)


# **2.시간 복잡도**
* 알고리즘이 수행되는 시간이 입력 크기에 따라 어떻게 변하는지를 분석한 개념


### 2-1. 빅오 표기법
  * 시간 복잡도를 분석할때 가장 많이 사용되는 표기법
  * 입력 크기가 커질때의 최악의 경우를 표현해 주는 방법
  * 0(1) : 상수 시간 복잡도
    * 입력 크기에 산관없이 항상 일정한 시간이 걸리는 경우
    * 예) 배열에서 인덱스로 특정값을 찾는 것(arr[0])

* 0(logn) : 로그 시간 복잡도
  * 입력 크기가 커져도 시간이 급격히 늘어나지 않는 경우
  * 예) 이진 탐색 트리 알고리즘

* 0(n) : 선형 시간 복잡도
  * 입력 크기 n에 비례해 시간이 늘어나는 경우
  * 예) 배열에서 값을 하나씩 확인하며 찾는 경우
*0(n^2)  : 이차 시간 복잡도
  * 입력 크기에 따라 시간이 n의 제곱으로 늘어나는 경우
  * 예) 버블 정렬처럼 중첩된 반복문이 있을때
  
*O(1) < O( logn ) < O(n) < O(nlogn ) < O( n^2 ) < O( 2n ) < O(n!)  
n(n+1)/2

### 2-2. 실제 알고리즘을 예로 시간 복잡도와 빅오 표기법 알아보기

# 1부터 n까지 합을 구하는 알고리즘
# 방법1
def sum_all(n):
  total = 0
  for num in range(1, n+1):
    total += num
  return total
  
sum_all(100) #빅오 표기법 : o(n)
-->
5050


#1부터 n까지 합을 구하는 알고리즘
# 방법 2
def sum_all(n):
  return int(n * (n+1) / 2)

sum_all(100) # 0(1)
-->
5050


어떤 알고리즘이 좋은지 객관적으로 비교하기 위해 빅오 표기법 들 시간 복잡도 계산법을 사용하는 이유
# **3. 공간 복잡도**
알고리즘이 실행될떄 얼마나 많은 메모리(공간)을 사용하는지 분석하는 개념

### 3-1. 공간 복잡도의 구성 요소
* 고정 공간 : 알고리즘이 항상 사용하는 메모리 양으로 입력 크기에 상관없이 일정함
  - 예) 함수 정의시 사용하는 함수 공간
* 가변 공간 : 입력 크기에 따라 달라지는 양
  - 예) 배열이나 리스트를 동적으로 생성할때 입력 데이터에 따라 메모리 변화량


#배열 arr은 입력으로 주어진 데이터이므로 공간 복잡도 계산에 포함되지 않음
# 가변 공간 : 입력 크기가 상관없이 항상 하나의 변수를 사용하므로 0(1)
def find_max(arr):
    max_value = arr[0]
    for num in arr:
      if num > max_value:
        max_value = num
    return max_value
-->
find_max([10,50,20,30])
-->
50


#고정공간 :arr은 입력으로 주어진 데이터이므로 제외
# 가변 공간 : 새로운 doubled 배열의 크기는 입력 배열 arr의 크기와 같으므로 크기 n에 비례해 메모리를 사용
def double_arr(arr):
    doubled = []    #새로운 리스트를 만듦(추가 메모리 공간)
    for num in arr:
      doubled.append(num * 2)
    return doubled
    
    
double_arr([10,20,30,40])
-->
[20, 40, 60, 80]


#입력 공간 : 함수는 단일 정수 n을 입력으로 받아 입력 공간은 거의 차지하지 않음
#가변 공간 : 제귀 호출이 일어날때마다 각 호출이 스택에 저장되어여 함 최대 n번의 호출이 스택에 쌓임
def fibonacci(n):
    if n <= 1:
      return n
    else:
      return fibonacci(n-1) + fibonacci(n-2)
      
#재귀 알고리즘은 시간 복잡도 및 공간 복잡도가 매우 나쁘다는 문제가 있음
#메모이제이션 같은 최적화 기법을 사용하는 것이 권장
fibonacci(4)
-->
3


### 3-2. 공간 복잡도 최적화 방법
* 메모이제이션(Memoization) :같은 계싼을 여러번 하지 않도록 계산한 값을 저장해서 사용하는 방법
* in-place Sorting : 배열을 정렬할때 새로운 배열을 만들지 않고, 입력 배열을 직접 정렬하는 방법
예 퀵정렬 -->공간 복잡도 (log n)
* 동적 프로그래밍(Dynamic Programming) : 메모이제이션과 계산한 결과를 테이블에 저장하며, 중복 계산을 피함으로써 시간과 공간 복잡도를 모두 줄일 수 있음