Big-O 표기법

C#과 유니티로 만드는 MMORPG 게임 개발 시리즈 강의를 수강하며 배운 내용과 자료구조 교재로 보충 공부한 것들을 한 번에 모아 정리해보았다.

---

• Big-O 표기법이란?
  - 함수 T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것.
  - 이를 위해서 데이터 수의 증가에 따른 연산횟수의 증가 형태를 표현한다.
  - 즉, 입력 N(데이터)의 크기(수의 증가)에 따라 성능이 영향(연산횟수 증가)을 받는 정도를 나타낸다.
  
  
  
• Big-O 표기법을 사용하는 이유
  - 두 알고리즘 A와 B의 효율을 비교할 때 다음과 같은 문제가 발생함
  
  1) A와 B의 속도를 비교하는데 정확한 기준이 없기 때문에 애매모호해짐
  2) 알고리즘을 비교하기 위해 프로그램을 짜서 실행 속도를 비교하는 것은 환경에 의존적이라 정확하지 않을 수 있음
  3) 입력이 적은 구간과 많은 구간에서 성능이 확연하게 차이가 나는 경우가 존재함
  
  - Big-O 표기법은 상술한 문제를 해결하기 위한 대안으로 사용됨.
  
  
• Big-O 표기법의 사용
  - 1단계 : 대략적인 계산
  : 수행되는 연산(산술, 비교 대입 등)의 개수를 대략적으로 판단한다.
  ex. 단순히 N+N을 리턴하는 ADD 함수는 1개의 연산을 수행한다.
  1개의 for문으로 I를 N번까지 반복하여 값을 더하고 그 합을 리턴하는 ADD 함수는 N+1개의 연산을 수행한다.
  2개의 for문으로 I와 j를 N번까지 반복하여 값을 더하고  그 합을 리턴하는 ADD 함수는 N^2+1개의 연산을 수행한다.
  
  - 2단계 : 대장만 남긴다
  : T(n)이 다항식으로 표현된 경우, 최고차항의 차수가 Big-O가 된다. 따라서 다음과 같은 규칙 2가지를 적용한다.
  1) 영향력이 가장 큰 대표 항목만 남기고 삭제
  2) 상수는 무시한다(ex. 2N => N)
  
  ex. 빅오를 따져볼 항목을 분석한 결과 O(1+N+4*N^2+1)이 되었다면, ()안의 식중에서 가장 차수가 높은 4*N^2만 남기고 모두 삭제한다. 이어서 상수는 무시한다는 규칙이 있기 때문에 앞의 4는 무시한다.
  결과적으로 해당 식(T(n))의 빅오는 O(N^2)가 된다.
  
  
  
• 대표적인 Big-O
  - O(1) : 상수형 빅-오라고 한다. 데이터 수에 상관없이 연산 횟수가 고정인 유형의 알고리즘을 뜻한다. 만약 3회 진행되는 알고리즘이라 하더라도 표기는 O(1)로 통일한다. 스택에서의 Push, Pop을 할때나 Hash Table을 이용해 접근하는 경우가 이와 같다.
  
  - O(logn) : 로그형 빅-오라고 한다. 데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘을 뜻한다. 이진트리의 시간 복잡도가 이와 같다.
  
  - O(n) : 선형 빅-오라고 한다. 데이터의 수와 연산횟수가 비례하는 알고리즘을 뜻한다. for문, 트리순회, linked list 순회의 시간 복잡도가 이와 같다.
  
  - O(nlogn) : 선형로그형 빅-오라고 한다. 데이터 수가 두 배로 늘 때, 연산 횟수는 두 배를 조금 넘게 증가하는 알고리즘을 뜻한다. 퀵 정렬, 병합 정렬, 힙 정렬, 분할 정복 방식으로 설계된 알고리즘이 해당된다.
  
  - O(n^2) : 다항형 빅-오라고 한다. 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 뜻한다. 이중으로 중첩된 반복문, 삽입 정렬, 거품 정렬, 선택 정렬 내에서 발생한다.
  
  - O(2^n) : 지수형 빅-오라고 한다. 연산 횟수가 지수적으로 매우 빠르게 증가하는 알고리즘을 뜻한다. 피보나치 수열이 이와 같으며 성능적인 면을 따져보면 현실적으로 사용하기에 무리가 있다.
  
  
  
• Big-O 표기의 성능(수행시간, 연산횟수) 대소 비교
  : O(1)-상수함수 < O(logn)-로그함수 <O(n)-선형함수 < O(n^2)-다항 함수 < O(2^n)-지수 함수)