빅오(Big-O) 표기법

복잡도(Complexity)

복잡도는 알고리즘의 성능을 나타내는 척도이다.

시간 복잡도와 공간 복잡도로 나눌 수 있다.

시간 복잡도는 속도에 해당하는 알고리즘의 수행 시간 분석 결과를 말한다.

공간 복잡도는 메모리 사용량에 대한 분석 결과를 말한다.

+추가

알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다.

빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용된다.

시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.

시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서 빅오(Big-O), 빅오메가(Big-Ω), 빅세타(big-Θ) 표기법 등이 있다.

 

✏️시간 복잡도(실행 시간) = 얼마나 오래 걸리는지, 알고리즘의 수행 시간이 얼마인지

✏️공간복잡도(실행 공간) = 얼마나 메모리를 차지하는지, 알고리즘이 공간을 얼마나 필요로 하는지

 

🤷‍♀️빅오(Big-O) 표기법?

---

빅오 표기법은 알고리즘의 효율성을 표기해주는 분석 방법이다.

효율성 판단 기준은 위에서 설명한 시간 복잡도, 공간 복잡도이다.

보통 실행속도가 메모리 사용량보다 중요하기 때문에 성능을 판단할 때는 시간 복잡도에서 영향력이 가장 큰 부분을 차지한다.

 

빅오 표기법은 기본적으로 알고리즘 '최악의 경우'를 가정하고 알고리즘의 성능을 판단(측정)한다.

아래 예제의 시간 복잡도는 O(1)로 표현한다.

연산이 딱 한번만 일어나기 때문이다.

let a = 1;
let b = 2;
console.log(a + b);

다음의 예제는 O(n)이라고 표현한다.

데이터 개수를 n개라고 했을 때 n번의 연산이 일어나기 때문이다.

O(n)은 선형 시간이고, i는 0부터 n-1까지 n번의 연산을 수행해야 한다!라는 것을 기억하자

// O(n)의 시간 복잡도
let arr = [1, 2, 3, 4, 5];
let sum = 0;
for(let in arr) {
	sum += i;
}

function bigoexample(n){
	for(let i = 0; i < n; i++){
    console.log(i);
    }

O(n^2), O(n^3)의 시간복잡도의 예제를 보자

// 이중 for문
function bifoexample(n){
	for(let i = 0; i < n; i++){
    console.log(i);
    for(let j = 0; j < n; j++){
    console.log(j);
    }
  }
}
// 삼중 for문

function bifoexample(n){
	for(let i = 0; i < n; i++){
    console.log(i);
    for(let j = 0; j < n; j++){
    console.log(j);
    for(let k = 0; k < n; k++){
    console.log(k);
      }
    }
  }
}

 

빅오 표기법 종류

위와 같이 다양한 빅오 표기법들이 있다.

 

✔️ O(1) : 상수 시간 (데이터 수에 상관X, 연산 횟수 고정)

✔️ O(log n) : 로그 시간 (데이터 수 증가율 > 연산횟수 증가율) => 이진트리

✔️ O(n) : 선형 시간 (데이터 수 & 연산횟수 비례) => for문

✔️ O(n* log n) : 로그 선형 시간 (데이터의 수 2배 증가 → 연산 횟수 2배 조금 넘게 증가)

=> 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

✔️ O(c^n): 지수 시간 (지수적으로 무섭게 증가..) => 피보나치수열?

 

우리가 만약 스택이라는 자료 구조를 선택해서 자료를 삽입하고 삭제하고 검색하는 일련의 과정을 거친다고 생각해보자.

이때 우리가 자료를 삽입, 삭제, 검색하는 일련의 행동들이 정확히 컴퓨터 상에서 몇 초 동안 수행되는지 정확히 알 수는 없다.

그렇기 때문에 우리는 몇 초 동안에 수행되는지가 아니라 어떤 연산을 하는데 몇 차례의 과정을 거치는지 횟수를 세는 방법으로 대략적인 소요 시간과 효율성을 측정할 수 있다.

이렇게 수행되는 연산의 수를 가지고 계산할 때에는 알고리즘에서 중요하지 않는 값들은 최대한 무시한다.

이 때 연산 과정을 간편하게 표기해서 쓸 수 있는 수학적인 표기법을 Big O(빅오)라고 부른다.

 

O(1)이라는 표현에서 1은 constant 즉, 상수 시간을 말한다.

우리가 스택에 어떤 자료를 추가할 때를 생각해보자.

스택에 자료를 추가할 때는 항상 스택의 맨 위에 자료를 push 하기만 하면 된다.

즉, 자료의 개수가 몇 개인지와 같은 다른 어떤 사항도 고려할 필요 없이 그냥 새로운 자료를 기존의 자료 맨 위에 올리기만 하면 된다는 뜻이다.

그러므로 한 번의 operation으로 자료의 삽입이 수행되므로 O(1)이라고 표기할 수 있다.

O(1)이라는 것은 단 한 번의 연산이 된다는 뜻은 아니다.

어떤 작업을 수행할 때마다 항상 동일한 작업만을 수행한다면 그 작업들을 뭉뚱그려서 O(1)이라고 표현할 수 있다.

그러므로 O(1)은 한 번의 연산을 수행한다는 뜻이 아니라 매 번 동일한 작업을 수행한다는 뜻이다.

 

자료를 삭제할 때도 마찬가지이다.

자료의 개수가 몇 개이던지 그냥 맨 위에 있는 자료를 pop 하면 되므로 자료의 삭제 또한 O(1)으로 표기할 수 있다.

 

그렇다면 자료의 검색은 어떨까?

만약에 스택에 5개의 블록이 쌓여있다면 우리는 맨 위의 블록에서부터 맨 마지막 블록까지 순차적으로 검색하여 자료를 찾아야 할 것이다.

운이 좋게 첫 번째 블록이 우리가 찾는 블록이었다면 한 번의 검색으로 답을 찾을 수 있겠지만 만약에 맨 마지막 블록이 우리가 찾는 블록이라면 우리는 맨 마지막 블록이 나올 때까지 5번의 검색 과정을 거쳐야 할 것이다.

그러므로 스택의 검색 횟수는 가장 최악의 경우인 O(n)으로 표기할 수 있다.

 

자료구조 & 시간 복잡도

 

1. Arrays(배열)

할당(Assign)	O(n)	바로 접근 후 덮어쓰기 가능
삽입(Insert)	O(n)	하나씩 옮겨야 함 (최악의 경우 모든 요소를 옮겨야 함)
삭제(Remove)	O(1)	삽입처럼 삭제후 하나씩 옮겨야 함
검색(Lookup - position)	O(1)	특정위치 데이터 가져오기 바로 접근 가능
검색 (Find - value)	O(n)	특정 값 찾기 하나씩 비교해서 찾아야 함

 

2. Linked List(연결 리스트)

할당(Assign)	O(n)	head부터 다음으로 계속 넘어가며 비교 필요
삽입(Insert)	O(1)	검색 이후  → O(1) / 검색 포함 → O(n)
삭제(Remove)	head → O(1) middle → O(n)	-
검색(Lookup - position)	O(n)	head부터 다음으로 계속 넘어가며 비교 필요
검색 (Find - value)	O(n)	head부터 다음으로 계속 넘어가며 비교 필요

 

Doubly-Linked List(이중 연결 리스트)는 자신의 양쪽 노드를 모두 참조하기 때문에, 삭제 과정이 단일 연결 리스트보다 빠르다.

하지만 메모리를 많이 차지한다.

 

 

 

빅오 표기법의 성능

O(1) > O(log n) > O( n) > O( n* log n ) > O( n²) > O( n³)  > O( 2n ) > O( n! )
// 왼쪽으로 갈 수록 효율적, 맨 오른쪽은 비효율적이다.