시간 복잡도

왜 알고리즘 복잡도가 필요한가?

 

어떤 문제를 푸는데 정답이 없다. 알고리즘이 다양할 수 있다.

한가지 문제를 해결하기 위해 여러가지 알고리즘이 있을때 어떤것이 가장 좋은가? 를 정할 기준이 필요했고

알고리즘 복잡도가 고안됐다. 

 

`` 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해 복잡도가 고안됐다.

 

알고리즘의 복잡도 계산 항목중 중요한 두가지

1. 시간복잡도: 알고리즘 실행 속도

2. 공간복잡도: 알고리즘이 사용하는 메모리 사이즈 (변수를 몇개 선언했는지)

 

-시간 복잡도를 이해하고 계산할수 있어야 한다.

 

알고리즘 시간 복잡도의 주요 요소

-반복문을 어떻게 구성했는지에 따라 알고리즘의 성능이 달려있다.

 

ex) 서울에서 부산을 가는데 다음과 같이 항목을 나누었을 때, 가장 총 시간에 영향을 많이 미칠 것 같은 요소는?

 

자동차로 서울에서 부산가기

1. 자동차 문열기
2. 자동차 문닫기
3. 자동차 운전석 등받이 조정하기
4. 자동차 시동걸기
5. 자동차로 서울에서 부산가기 (시간이 젤 많이 걸리는 부분)
6. 자동차 시동끄기
7. 자동차 문열기
8. 자동차 문닫기

알고리즘 성능 표기법

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

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

 

대문자 O 표기법

• O(입력) 
  -입력 n에 따라 결정되는 시간 복잡도 함수
  -O(1), O(𝑙𝑜𝑔𝑛logn), O(n), O(n𝑙𝑜𝑔𝑛logn), O(𝑛2n2), O(2𝑛2n), O(n!)등으로 표기함
  -입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있다.
  -O(1) < O(logn) < O(n) < O(nlogn) < O(𝑛2n2) < O(2𝑛2n) < O(n!)
  참고 log n의 베이스는 2-log2n
• 단순하게 입력n에 따라, 몇번 실행이 되는지를 계산하면 된다.
  

 

연습1:  1부터 n까지의 합을 구하는 알고리즘 작성해보기

 

1.

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

n에 100을 대입한다고 했을때 5050의 결과 값을 얻을 수 있다.

그럼 이 코드의 시간 복잡도는 O(n)이 되게 된다 n의 값에 따라 반복이 달라지기 때문!!다른 방법

2.

• 𝑛(𝑛+1)2

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

위와 같은 공식을 사용한다면 위 코드의 시간복잡도는 O(1)

2번째 코드가 효율이 좋은것을 시간복잡도를 통해 알 수있다.