[Interview] BigO가 무엇인지 설명해주세요

BigO 표기법

● BigO란 점근 표기법 중 하나입니다. 점근은 알고리즘의 수행 시간을 대략적으로 나타내는 방법입니다.

● 접근 표기법의 종류 :  ○ O(Big O) 표기법 : 알고리즘 성능이 최악인 경우(수행 시간의 상한)를 나타낼 때 사용  ○ Ω(Big Omega) 표기법 : 알고리즘 성능이 최선인 경우(수행 시간의 하한)를 나타낼 때 사용  ○ Θ(Big Theta) 표기법 : 알고리즘이 처리해야하는 수행 시간의 상한과 하한을 동시에 나타냄

 

● BigO는 알고리즘의 성능이 최악인 경우를 나타냅니다.
알고리즘을 사용하는 어떤 경우에도 보장되는 알고리즘 성능입니다.
 최악의 경우에 대한 알고리즘 수행 시간이 가장 쓸모가 많다 보니
가장 많이 사용되는 알고리즘 성능 표기법입니다.

 

● 가장 널리 사용되는 규모 함수들을 최선(가장 효율적)에서 최악(가장 비효율적)의 순서로 나열

최선... → ...최악

 

상수 시간

● 상수 시간 복잡도(Constant Time Complexity)

  - 어떤 알고리즘이 n의 크기에 관계없이 동일한 단계만 필요한 경우입니다.

  - '알고리즘이 상수 시간으로 실행된다'라고 말합니다.

  - 상수 시간 알고리즘을 BigO 표기법으로 표기하면 O(1)입니다.

 

● 예를 들어,
 온라인 서점을 운영한다고 했을 때, 첫 방문 고객에게 무료로 책을 선물합니다.
 이 고객을 customers 리스트에 저장한다면...

// 코드로 나타내면?
let free_books = cusomters[0];

// 알고리즘 단계를 나타내는 수식
T(n) = 1

 

● 데이터 세트가 아무리 커지더라도 알고리즘의 실행 시간이 변하지 않기 대문에 가장 효율적인 알고리즘입니다.

 

로그 시간

● 로그 시간 복잡도(Logarithmic Time Complexity)

  - 두 번째로 효율적인 시간 복잡도입니다.

  - 실행을 반복할 때마다 알고리즘의 탐색 범위를 1/2로 줄여 나가는 이진 탐색과 같은 알고리즘에서 사용합니다.

  - BigO 표기법으로는 O(log n)으로 표기합니다.

 

선형 시간

● 선형 시간 복잡도(Linear Time Complexity)

  - 선형 시간으로 실행되는 알고리즘은 데이터의 크기가 커지는 만큼 같은 비율로 늘어나는 알고리즘입니다.

  - BigO 표기법으로는 O(n)으로 표기합니다.

 

● 예를 들면

 매일 첫 번째로 방문하는 고객에게 무료로 책을 선물하는 대신, 고객 리스트를 훑어보면서 이름이 B로 시작하는 고객에게 책을 선물한다고 가정합니다. 고객 리스트가 알파벳 순으로 정렬되어 있지 않다면 B로 시작하는 이름을 하나씩 탐색하며 찾습니다.

// 코드로 표현하자면?
let free_book = false;
let customers = ["Lexi", "Briteny", "Danny", "Bobbi", "Chris"];
for (let customer in customers) {
	if (customer[0] === 'B') {
   	console.log(customer);
    }
}
	
        
// 알고리즘 단계를 나타내는 수식
O(n) = n

 

● 데이터 세트가 커지는 만큼 알고리즘의 실행에 필요한 단계가 같은 비율로 늘어납니다.

 

선형 로그 시간

● 선형 로그 시간(Log-Linear Time)

  - 복잡도는 선형 시간 복잡도를 곱한 만큼 커집니다.

  - BigO 표기법으로는 O(n log n)으로 표기합니다.

  - 데이터 세트를 작은 부분으로 나누고, 독립적으로 처리하는 형태입니다.

  - 병합 정렬과 같은 효율적인 정렬 알고리즘이 선형 로그 시간 복잡도를 따릅니다.

 

 

2차 시간

● 2차 시간 복잡도(Quadratic Time Complexity)

  - 2차 시간으로 실행되는 알고리즘 복잡도는 n의 제곱에 정비례합니다.

  - BigO 표기법으로는 O(n^2)으로 표기합니다.

 

● 2차 시간 복잡도 알고리즘 예제

// 코드로 표현한다면?
let numbers = [1, 2, 3, 4, 5];
for(let i = 0; i < numbers.length; i++) {
	for(let j = 0; j < numbers.length; j++) {
    	let x = i + j;
        console.log(x);
	}
}

// 알고리즘 단계에서 나타내는 수식
O(n) = n**2

 

● 삽입 정렬, 버블 정렬과 같은 정렬 알고리즘들이 2차 시간 복잡도를 사용합니다.

 

3차 시간

● 3차 시간(Cubic Time)

  - 알고리즘의 시간 복잡도는 n의 세제곱에 정비례합니다.

  - BigO 표기법으로는 O(n^3)으로 표기합니다.

// 코드로 표현한다면?
let numbers = [1, 2, 3, 4, 5];

for(let i = 0; i < numbers.length; i++) {
  for(let j = 0; j < numbers.length; j++) {
    for(let h = 0; h < numbers.length; h++) {
        let x = i + j + h;
        console.log(x);
    }
  }	
}
      
// 알고리즘 단계에서 나타내는 수식
O(n) = n**3

 

● 쉽게 생각하면 for문이 2번 돌면 2차 시간, 3번 돌면 3차 시간 복잡도라 칭합니다.

   (통계 부분에서는 어쩔 수 없이 사용되지만 최대한 지양되어야 하는 시간 복잡도입니다)

 

지수 시간

● 지수 시간 복잡도(Exponential Time Complexity)

  - 최악의 시간 복잡도입니다.

  - 지수 시간으로 실행되는 알고리즘의 복잡도는 데이터 크기의 지수식으로 표현됩니다.

  - 어떤 상수 c를 n 제곱한 만큼 실행 단계가 커지는 알고리즘입니다.

  - BigO 표기법으로는 O(c^n)으로 표기합니다.

// 코드로 표현한다면?
let pin = 931;
let n = len(pin);
for (let i = 0; i < 10 ** n; i++) {
	if (i === pin) {
    	console.log(i);
    }
}

 

● 최악의 알고리즘인데 언제 사용합니까?

  - 비밀번호 입력을 무제한으로 입력할 수 있는 허술한 사이트에서 모든 경우의 수를 시도할 때 사용합니다.

  - 무차별 대입 알고리즘(Burte-Force Alogrithm)이라고도 합니다.

 

Q : 복잡도가 왜 중요할까요?

A :
 프로그램을 사용하는 데 있어서 실행시간이 오래 걸린다면 사용자 경험에서 좋지 않은 현상입니다.
결국 프로그램을 만드는 이유는 사용자가 존재하고 어떠한 목적에 의해 탄생하게 됩니다.
그런 의미에서 상수 시간 알고리즘(O(1))을 최대한 사용해서 프로그램을 구현한다면
이 프로그램을 사용하는 입장에서도 빠르게 프로그램을 사용할 수 있어 이득이고,
서비스하는 입장에서는 사용자 확보가 가능하고 지속적인 서비스를 이어 나갈 수 있습니다.
프로그램을 작성할 때도 가독성도 좋아지기 때문에 최대한 효율적으로 알고리즘을 선택해야 합니다.