Big O notation

빅오 표기법

알고리즘이 얼마나 빠른지 표시하는 방법
속도를 시간 단위로 세지 않는다. 연산 횟수를 비교하기 위한 방법이다.
수행해야 할 일이 많아질 때 알고리즘에 걸리는 시간이 어떤 식으로 증가하는지를 알 수 있다.

• 최악의 실행시간을 나타낸다.
  (ex.단순탐색의 경우 최악의 경우 n번 서치.)
• 최악의 경우에 대한 실행 시간 이외에도 평균 실행시간을 살펴보는 것도 중요하다.

리스트의 크기가 n이라고 가정했을시

• 단순탐색 : 원소를 하나씩 확인하므로 n번을 연산
  • 빅오표기법에 따른 실행시간 O(n)
• 이진탐색 : log n번의 연산이 필요
  • 빅오표기법에 따른 실행시간 O(log n)

많이 사용하는 빅오 실행시간의 예

• O(log n) : 로그시간 ex.이진탐색
• O(n) : 선형시간 ex.단순 탐색
• O(n*log n) : ex.퀵 정렬과 같이 빠른 정렬 알고리즘
• O(n^2) : ex.선택 정렬과 같이 느린 정렬 알고리즘
• O(n!) : ex.외판원 문제같이 정말 느린 알고리즘

예시 : 외판원 문제
실행시간이 증가하는 것이 엄청나서 더 이상 알고리즘을 향상시키는 것이 불가능하다고 판단되는 문제.

/*

한 외판원이 다섯개의 도시를 방문해야 한다. 
가장 짧은 거리를 통해 다섯 개의 도시를 모두 방문하고자 한다.

1. 도시를 방문하는 모든 경로를 살펴본다.
2. 전체 거리를 더해서 가장 짧은 경로를 택한다.

도시가 5개라면 120가지 경우가 있다.
도시가 6개가 되면 연산 횟수는 720번이 된다.
도시가 7개가 되면 연산 횟수는 5,040번이 된다.

n개의 도시가 있을시 결과 계산에 n!번의 연산이 필요하게 된다.

좋지 않은 방법이지만 다른 방법이 알려지지 않은 알고리즘 문제이다.
*/

정리

• 이진 탐색은 단순 탐색보다 매우 빠르다.
• O(log n)은 O(n)보다 빠르다. 리스트 원소 개수가 증가할수록 더 빨라진다.
• 알고리즘의 속도는 시간으로 측정하지 않는다.
• 알고리즘의 시간은 어떻게 증가하는가로 측정한다.
• 알고리즘의 시간은 빅오 표기법으로 나타낸다.

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘