복잡성

시간복잡도

규칙

• 입력은 항상 0 이상이다.

  • 그렇기에 복잡도는 0보다 크다고 가정.

• 함수는 많은 입력값이 있을 때 더 많은 작업을 하게된다.

  • 입력값이 많은데 더 적게 작업하는 함수는 있을 수 없다.

• 모든 상수를 삭제한다.

  • 단순히 곱하는 수일 뿐이다.

• 큰 값들에 대해서만 생각한다.

• 낮은 차수의 항은 무시한다.

  • 다양한 차수 항을 가지고 있는 함수가 있다면 높은 항에 대한 값을 복잡도 기준으로 삼는다
  • n³ + n² + n + 5 일때 n³에 대한 알고리즘이라고 말한다.

• 로그에서는 로그의 밑은 무시한다.

  • Math.log(2) == 1n(2)
    

  • 그렇기에 밑을 고려하지 않은 log n 알고리즘이라고 부른다.

• 2n = O(n) == 2n ∈ (O)n

알고리즘 종류 정리

• 1, C -> constant time
  • 상수 시간에 작동하는 알고리즘
  • 한번만 계산하면 되는 경우
  • n과는 독립적인 관계다.
• log n
  • trees에 관련된 함수는 일반적으로 log n의 복잡도를 가진다.
  • 무언가를 반으로 나누거나 곱할때 이 알고리즘을 사용한다.
• n
  • Once per item
  • 각 요소마다 한번씩 작업하는 경우
  • 리스트 탐색, 연결 리스트 탐색 등
• n²
  • Compare all * all
  • 모든요소를 서로 비교하는 경우
  • n제곱의 시간이 걸린다.
  • bubble sort
• n!
  • Traveling sales
  • 외판원 문제
  • 최단경로 찾기

빅오 표기법

알고리즘의 효율성을 표기하는 표기법이다.

다른 알고리즘과의 차이를 확인할 수 있다.

Big O

• 같거나 빠르다.

Little o

• 빠르지만 같지는 않다.

Big Ω

• 기준 알고리즘보다 같거나 더 느린 알고리즘을 비교할때는 빅 오메가라고 한다.

Little ω

• 느리지만 같지 않다.

Θ

• 완전히 똑같다.

빅오 표기법 예시

1. n^4/3 = O(n log n) -> false

   • 1000^4/3 = 1000 log(10000)

   • 10000 = 1000 * 3

2. 3n³ + 4n² + 5n + 6 = Θ(n³)

   • True