[파이썬 알고리즘] 4장 - 빅오

• 빅오
  • 빅오는 점근적 실행시간을 표기할 때 사용된다.
  • 점근적 실행시간이란, 입력값이 커질 때 함수의 실행 시간의 추이를 말한다.
  • 즉, 절대적인 소요 시간을 나타내는 것이 아니라,
    입력값에 따라 실행시간이 어떠한 추이로 달라지는 지를 표기한 것
  • 점근적 실행시간은 시간복잡도라고 할 수 있다.
  • 빅오로 시간복잡도를 표현할 경우 최고차항만을 표기하고, 또한 상수는 무시한다.
    
    
• 빅오 표기법의 종류
  • O(1)
    • 입력값이 아무리 커져도 실행 시간이 일정하다.
    • (실행 시간이 짧은 상태로 일정할수도, 긴 상태로 일정할수도 ...)
  • O(log n)
    • 입력값이 커짐에 따라 실행 시간 증가하지만,
    • 입력값이 커지는 속도 대비 실행 시간의 증가 속도가 느리다
  • O(n)
    • 입력값만큼 실행시간이 달라진다.
    • 이러한 알고리즘을 선형 시간 알고리즘이라고 한다.
  • O(n log n)
    • 대부분의 정렬 알고리즘이 이에 해당한다.
  • O(n^2)
    • 버블 정렬과 같은 정렬 알고리즘이 여기에 속한다
  • O(2^n)
    • 피보나치 수를 재귀로 계산하는 알고리즘
  • O(n!)
    • traveling salesman problem을 브루트 포스로 풀이하는 경우
      
      
• 대부분의 경우 시간과 공간은 trade-off 관계가 있다.
  • 시간이 적게 걸리면 메모리 공간 많이 사용하고
  • 시간이 많이 걸리면 메모리 공간 적게 사용한다.
    
    
• 상한과 최악
  • 빅오는 최선, 최악, 평균 경우 수행 시간의 상한을 의미한다.
  • 하한을 의미하는 것은 빅오메가, 평균을 의미하는 건 빅세타 존재
    
    
• 분할 상환 분석(armotized cost)
  • 시간, 또는 메모리 분석하는 알고리즘의 복잡도 계산하는 경우
  • 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도 계산
  • 빅오는 최악의 경우가 거의 발생하지 않음에도 불구하고, 최악을 가정하고 복잡도를 계산한다. 이 문제점에 주목하여 나온 개념이다
  • 쉽게는 '평균'의 정보를 준다고 생각하면 될 것 같다.

zeddios.tistory.com/60

알고리즘 ) Amortized Analysis

• 병렬화
  • 알고리즘 자체의 시간복잡도 외 알고리즘의 병렬화가 가능한 지가 알고리즘의 우수성을 평가하는 척도 중 하나가 되었다!!