자료구조 - 알고리즘 복잡도

알고리즘 복잡도

• 필요성 : 다양한 알고리즘 중 어느 알고리즘이 더 좋으니를 분석하기 위해, 복잡도를 정의하고 계산함
• 복잡도 계산항목
  - 시간 복잡도 : 알고리즘 실행속도
  - 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈
• 알고리즘 성능 표기법
  
  • Big O (빅-오) 표기법: O(N)
    • 알고리즘 최악의 실행 시간을 표기
    • 가장 많이/일반적으로 사용함
    • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문
  • Ω (오메가) 표기법: Ω(N)
    • 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
  • Θ (세타) 표기법: Θ(N)
    • 오메가 표기법은 알고리즘 평균 실행 시간을 표기

※ 시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인

    Big-O 표기법을 중심으로 익히면 됨

 

예시 : 1부터 n까지의 합을 구하는 알고리즘 작성해보고 비교하기

 

알고리즘(1) 시간 복잡도 = O(n)

 

알고리즘(2) 시간 복잡도 = O(1)

O(n) vs O(1)  → 알고리즘 2의 성능이 좋다.