빅오 표기법

시간 복잡도

Big-O 표기법은 컴퓨터 과학에서 알고리즘의 성능이나 복잡성을 설명하는 일반적인 수단입니다. 시간 복잡성은 연구를 계속 진행함에 따라 개발 환경의 중요한 측면이 될 것입니다. 프로그램을 분석하고 어떤 프로그램이 시간 복잡도(상수, 선형, 2차, 지수, 로그)에 속하는지 표시합니다.

O(1)- 일정한 시간:

상수 시간 복잡도는 입력 데이터 세트의 크기에 관계없이 항상 동일한 시간(또는 공간)에서 실행되는 알고리즘을 설명합니다. JavaScript에서 이것은 배열 내의 특정 인덱스에 액세스하는 것처럼 간단할 수 있습니다.

let array = [1, 2, 3, 4, 5];
array[0] // This is a constant time look-up

const removeLastElement = function(array) {
  let numberOfElementsToRemove = 2;
  while (numberOfElementsToRemove > 0) {
    array.pop();
  }
}; 
//This will also have a constant time look-up since the function is 
//only looking at a specific reference point within the array.

배열의 크기는 중요하지 않습니다. 배열의 특정 위치를 찾는 데도 같은 시간이 걸립니다. 따라서 함수에는 일정한 시간 조회가 있습니다.

O(N)-선형 시간:

선형 시간 복잡성은 입력 데이터의 크기에 정비례하여 복잡성이 증가하는 알고리즘 또는 프로그램을 설명합니다.

const numberRange = function(array) {
  for (let i = 1; i < array.length; i++) {
    console.log(array[i]);
  }
}; 
//This will have a linear time look-up since the function is
//looking at a every index in the array once.

이 예에서 조회 시간은 배열 내의 각 항목을 살펴볼 것이기 때문에 입력 크기와 직접적인 관련이 있습니다. 즉, 입력이 클수록 기능을 수행하는 데 걸리는 시간이 커집니다. 물론 배열에 1개의 인덱스만 있는 경우(즉, array.length === 1) 함수는 일정한 시간 조회를 갖습니다.

O(log(n)) — 로그 시간:

대수 시간 복잡도는 입력 크기의 대수에 비례하여 실행되는 알고리즘을 나타냅니다.

const partialRange = function(array) {
  for (let i = 1; i < array.length; i = i * 2) {
    console.log(array[i]);
  }
}; 
//This will have a logarithmic time look-up since the function is
 //looking at only searching through part of the array.

배열 길이가 전달될 때까지 숫자를 기록합니다. 이 기능은 특정 간격으로만 숫자를 기록합니다. 우리는 배열의 여러 부분에 대해 일정한 시간 조회를 반복할 것이며, 함수는 일정한 시간 조회를 가지지 않을 것입니다. 또한 함수는 배열의 모든 인덱스를 통과하지 않으므로 선형 시간 조회가 없습니다.

O(N²) — 2차 시간:

2차 시간 복잡도는 성능이 입력 데이터 세트의 제곱 크기에 정비례하는 알고리즘을 나타냅니다(선형을 생각하지만 제곱). 이 시간 복잡도는 데이터 세트 내에서 여러 번 반복할 때 발생합니다.

const hasDuplicates = function(array) {
  for (let i = 0; i < array.length; i++) {
    let item = array[i];
    if (array.slice(i + 1).indexOf(item) !== -1) {
      return true;
    }
  }
  return false;
}; 
//This will have a quadratic time look-up since the function is
//looking at every index in the array twice.
   console.log(hasDuplicates([2,4,2,3]))

첫 번째 부분에서 우리 함수가 적어도 한 번은 배열을 검색할 것이 분명하지만 차이점을 만드는 요소는 if 문에 있습니다. 여기에서 네이티브 indexOf 메서드를 사용하여 배열의 또 다른 조회를 수행합니다. 그렇게 함으로써 우리는 각 검색에서 동일한 배열을 두 번 전달하여 2차 시간 복잡도를 생성합니다.

O(2^N) — 지수 시간

지수 시간 복잡도는 입력 데이터 세트에 추가할 때마다 증가하는 알고리즘을 나타냅니다. 다른 기하급수적 성장 패턴을 알고 있다면 이는 거의 동일한 방식으로 작동합니다. 시간 복잡도는 매우 얕게 시작하여 끝까지 증가하는 속도로 증가합니다.

const fibonacci = function(number) {
  if (number <= 1) return number;
  return fibonacci(number - 2) + fibonacci(number - 1);
}; //This will have an exponential time look-up since the function 
   //is looking at a every index an exponential number of times.

console.log(fibonacci(4))  //3

피보나치 수는 재귀에 대한 이해를 연습하는 좋은 방법입니다. 피보나치 함수의 시간 복잡도를 줄이는 방법이 있지만 이 경우 이중 재귀 방법을 사용하여 지수 시간 복잡도를 갖는 방법을 보여줍니다. 간단히 말해서, 재귀적 인스턴스화는 숫자에서 0까지 모든 숫자를 전달합니다. 기본 케이스 if 문에 도달할 때까지 이 작업을 두 번(각 재귀 호출에 대해 한 번) 수행합니다.

참조:
https://medium.com/@ariel.salem1989/an-easy-to-use-guide-to-big-o-time-complexity-5dcf4be8a444
https://www.interviewcake.com/article/python/big-o-notation-time-and-space-complexity ?
https://www.bigocheatsheet.com