빅오 표기법 Big-O Notation 이란?

Big O Notation (빅 오 표기법)

컴퓨터 과학자는 서로 간에 시간 복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했다. 이런 개념을 형식화한 것이 빅 오 표기범이며. 이것을 사용해여 주어진 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다. 간단하게 말하자면 알고리즘의 효율성을 분석하기 위해 컴퓨터 공학자들이 쓰는 가장 기본적인 도구 중 하나이다.

 

빅 오는 특정 방식으로 알고리즘에 필요한 단계 수를 고려함으로써 일관성을 유지한다. 그리고 단순히 알고리즘에 필요한 단계 수만 알려주지 않는다. 데이터가 늘어날 때 단계 수가 어떻게 증가하는지 설명한다. 

 

빅 오 카테고리

O(N) : 선형시간을 갖는 알고리즘. 데이터 중가가 성능에 영향을 준다. 정확히는 데이터가 늘어날 때 정확히 그 데이터에 비례해서 단계 수가 증가하는 알고리즘유형이다. 

 

O(1) : 상수 시간을 갖는 알고리즘. "가장 빠른" 알고리즘 유형으로 분류. 데이터가 늘어나도 단계의 수가 증가하지 않는다. 

 

O(logN) : "오 로그 N". 로그 시간의 시간 복잡도. 데이터가 두 배로 증가할 때마다 한 단계식 늘어나는 알고리즘을 설명하는 빅 오. 

 

O(n²) : 이차시간 알고리즘. n이 증가할 때마다 단계 수가 n² 만큼 늘어난다고 보면된다. 값이 n개 이므로 n² 가 필요하다. 

 

O(n log n) : 배열의 원소가 n개 일 때 정렬에 필요한 단계수는 n x logN이다. 

 

O(2ᴺ) : 가장 느린 빅 오. O(logN)의 반대이다. 데이터가 1씩 커질 대 알고리즘에 필요한 단계수는 대략 2배씩 늘어나는 것. 

 

빅 오 표기범 예제

O(N) : for문

O(1) : Stack (push, pop)

O(logN) : 이진 검색

O(n²) : 이중반목문, 삽입정렬, 버블정렬,선택정렬

O(n log n) : 퀵 정렬, 병합정렬, 힙정렬

O(2ᴺ) : 피보나치 수열. (암호크래커문제)