TIL-078 | Big-O notation

🌈 Big-O notation

🧐 그동안 자료구조&알고리즘을 공부하면서 공부하는 이론마다 시간복잡도를 포함하여 학습을 했었다. 개념을 따로 공부하긴 했었기에 이해를 하곤 했었지만 조금 더 깊은 이해를 위해 Big-O notation에 대해 짚고 넘어가고자 한다.

Big-O notation이란?

• 알고리즘을 수행하는 데 걸리는 시간을 설명하는 시간 복잡도를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 빅오 표기법이다.
• 빅오로 표기할때는 최고차항만 표기하며, O(f(n))으로 나타낸다.
• 빅오 표기법은 상한(=가장 늦게 실행될 때)을 의미한다. 하한을 의미하는 빅오메가, 평균을 의미하는 빅세타 도 있지만 주로 빅오를 사용한다.

알고리즘의 시간복잡도

• 알고리즘의 복잡도를 판단하는 척도로는 시간복잡도와 공간복잡도 두 가지가 있으며, 이를 나타내는 대표적인 표기법으로 빅오 표기법을 사용하는 것이다.
• 시간복잡도는 알고리즘의 효율성을 나타낸다고 볼 수 있다.
• 공간복잡도는 알고리즘의 공간(메모리) 효율성을 나타낸다.
• 알고리즘은 연산이 많아질수록 그 속도가 오래 걸린다.
• 따라서 시간 복잡도는 알고리즘 내 연산의 횟수와 관계가 있다.
• 알고리즘에서 시간복잡도는 "n의 값이 증가함에 따라 처리 시간이 증가하는 정도" 라고 생각할 수 있다.

Big-O 표기법의 특징

• 상수항 무시
  : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.
  ex) O(2n) --> O(n)

• 영향력 없는 항 무시
  : 빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.
  ex) O(n2+9n+1) --> O(n2)

Big-O 표기법의 종류

✔ O(1) : 입력값에 상관없이 일정한 실행시간을 가지는 훌륭한 알고리즘이라 할 수 있다. 하지만 상수값이 상상 이상으로 클 경우 사실상 일정한 시간의 의미가 없다. 최고의 알고리즘이 될 수 있지만 그만큼 신중해야 한다.
👉 ex) 스택에서의 pop, push

✔ O(log n) : 로그는 매우 큰 입력값에서도 크게 영향을 받지 않는 편이다. 매우 견고한 알고리즘이다.
👉 ex) 이진 탐색 트리

✔ O(n) : 알고리즘을 수행하는데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간 알고리즘이라 부른다. 정렬되지 않은 리스트에서 최대 또는 최솟값을 찾는 경우가 해당되며 모든 입력값을 적어도 한 번 이상은 살펴봐야 한다.
👉 ex) for 문

✔ O(nlog n) : 병합 정렬등의 대부분 효율이 좋은 알고리즘이 이에 해당 한다. 아무리 좋은 알고리즘이라 할지라도 n log n 보다 빠를 수 없다. 입력값이 최선일 경우, 비교를 건너 뛰어 O(n)이 될 수 있다.
👉 ex) 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

✔ O(n^2) : 버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당 한다.
👉 ex) 이중 for 문, 삽입정렬(insertion sort), 버블정렬(bubble sort), 선택정렬(selection sort)

✔ O(2^n) : 피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당 한다. n^2와 혼동되는 경우가 있는데 2^n이 훨씬 더 크다.
👉 ex) 피보나치 수열

✔ O(n!) : 가장 느린 알고리즘으로 입력값이 조금만 커져도 계산이 어렵다.

성능 비교

• 위의 그래프에 나와 있는 시간 복잡도의 성능을 비교하면 다음과 같다.
  👉 상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수
  (왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.)

📝 Reference

1. https://noahlogs.tistory.com/27
2. https://holika.tistory.com/29
3. https://codermun-log.tistory.com/235