[Frontend/Javascript] 시간복잡도 (Big-O Chart)

알고리즘을 구현하는 법을 학습하기 전에 알고리즘이 얼마나 효과적인지 분석하는 법을 이해해야 합니다. 알고리즘이라고 언급하니 뭔가 거창한 로직이라도 되는 것 같지만, 실은 우리가 작성하는 하나의 함수라고 생각해도 문제가 없습니다.

 

이제 알고리즘의 최악의 복잡도를 측정하는 빅오 표기법에 대해 알아보겠습니다. 빅오 표기법은 시간 복잡도를 계산하는 가장 일반적인 방법입니다. 작업을 완료하는 데 필요한 단계와 관련하여 작업 실행 시간을 설명합니다.

Big O 표기법은 O (n) 형식으로 작성됩니다. 여기서 O는 "크기 순서"를 나타내고 n은 작업의 복잡성을 비교하는 대상을 나타냅니다.

 

 

# 일정한 복잡도 : O(1)

만약 다음과 같이 값을 그대로 출력하는 함수가 있다고 가정해봅시다.

 

function test(array) {
  console.log(array);
}

 

어떤 값을 넣어도, 아무리 많은 배열을 넣어도 한단계의 작업만 필요합니다. 따라서 O(1) 시간에 실행된다고 말할 수 있습니다.

 

---

# 선형 복잡도 : O(n)

선형 작업의 실행 시간은 그것의 입력값에 따라 달라집니다. 예를들면 위에서 처리한 한번의 출력을 데이터의 수에 따라서 달라진다고 가정해 봅시다. 그러면 배열의 수와 비례하여 출력량이 늘어날 것입니다. 입력받은 값에 비례하여 작업이 늘어나는 경우를 선형복잡성이라고 합니다.

 

function test (array) {
  for(let i=0; i<array.length; i++) {
    console.log(array[i]);
  }
}

 

---

# 2차 복잡도 : O(n^2)

위에서 정의한 반복문을 2중으로 겹쳐지는 작업. 즉, 함수 내에서 두번의 반복문이 필요로 하는 경우를 말합니다. 위에서 배열을 다음과 같이 이중 반복문으로 출력을 한다고 가정하면 실행시간은 n^2 에 비례하여 증가합니다.

 

function test (array) {
  for(let i=0; i<array.length; i++) {
    for(let j=0; j<array.length; j++) {
      console.log(array[j]);
    }
  }
}

 

---

# 대수 복잡도 : O(log n)

이것은 계산을 엄청 빠르게 만드는 알고리즘 유형입니다. 이후의 각 단계를 수행하는 데 걸리는 시간을 늘리는 대신, N에 반비례하는 크기로 시간을 줄입니다.

 

특정 번호에 대한 데이터베이스를 검색한다고 가정해 보겠습니다. 데이터 세트에서 숫자 100에 대해 20개의 숫자를 검색하려고 합니다. 이 예에서 20개의 숫자를 검색하는 것은 문제가 되지 않습니다. 하지만, 수백만명의 사용자 프로필 정보를 저장하는 데이터 세트를 다루고 있다고 상상해보십시오. 각 인덱스 값을 처음부터 끝까지 검색하는 것은 엄청나게 비효율적입니다. 특히 여러번 수행해야 하는 경우는 더욱 그렇습니다.

 

이진 검색을 수행하는 로그 알고리즘은 단계당 점점 더 작아지는 데이터세트의 절반만 살펴봅니다. 오름차순 숫자 세트가 있다고 가정하겠습니다. 알고리즘은 전체 데이터 세트의 절반을 검색하는 것으로 시작됩니다. 숫자를 찾지 못하면 방금 확인한 세트를 버리고 나머지 숫자 세트의 절반을 검색합니다.

 

 

위에서 설명한 것처럼 각 검색 라운드는 이전보다 더 작은 데이터 세트로 구성되어 각 후속 라운드가 수행되는 시간을 줄입니다.