대형 O 기호, 시간 및 공간의 복잡성에 대한 부드러운 소개

소개

나는 이미 소프트웨어 공학 분야에서 15년을 일했지만, 나는 컴퓨터 과학 전공의 졸업생이 아니다.그래서 나는 수업에서 데이터 구조나 알고리즘을 진정으로 배운 적이 없다.그럼에도 불구하고 이것은 내가 우수한 소프트웨어 엔지니어가 되는 것을 막지 못했다.
그러나 나는 항상 이 모든 것이 무엇에 관한 것인지 궁금해서 마침내 절대적인 기본 원리를 이해할 시간이 생겼다.나는 내가 배운 지식을 대부분의 비컴퓨터 과학 졸업생들이 인정할 수 있는 방식으로 나눌 수 있기를 바란다.
본고에서 우리는 다음과 같은 세 가지 개념을 연구할 것이다.

큰 O 기호

시간 복잡도

공간 복잡도

큰 O 기호

큰 O 기호는 컴퓨터 과학에서 알고리즘의 성능이나 복잡성을 설명하는 데 쓰인다.간단하게 말하면 알고리즘이 실행되는 데 필요한 시간과 시간의 추이에 따라 알고리즘의 입력이 얼마나 많은 메모리를 증가시킬 수 있는지를 나타내는 데 쓰인다.

큰 O 기호를 사용하면 입력이 클수록 실행할 때 입력의 증가 속도에 따라 실행할 때를 나타냅니다.
위에 기울임꼴로 강조 표시된 단어를 확장해 보겠습니다.

실행 속도가 얼마나 빠른지 - 일반적으로 프로세서 속도와 현재 컴퓨터에서 실행 중인 다른 프로그램에 따라 프로그램이 정확하게 실행되는지 확인하기 어렵다.따라서 우리는 실행할 때 직접 토론하지 않고 큰 O 기호를 사용하여 실행할 때의 성장 속도를 토론한다.

입력 대비 - 만약 우리가 직접 측정하여 운행할 때, 우리는 초와 분으로 속도를 표시할 수 있다.우리는 운행 중의 성장 속도를 측정하고 있기 때문에, 우리는 다른 물건으로 속도를 표시해야 한다.큰 O의 경우 입력한 크기는 "n"입니다.따라서 실행할 때 입력 크기의 순서(O(n) 또는 입력 크기의 제곱 순서(O(n²)가 증가한다고 할 수 있습니다.

입력이 커지면서 입력 크기가'n'이 매우 어렸을 때 우리의 알고리즘은 비싸 보이는 절차가 있을 수 있지만'n'이 커지면 결국 다른 절차에 의해 가려진다.대 O 기호 분석에 대해 우리가 더욱 관심을 가지는 것은 입력이 증가함에 따라 가장 빨리 증가하는 것이다. 왜냐하면'n'이 매우 커지면서 다른 모든 것이 곧 어두워지기 때문이다.

시간 복잡성

이전 절에서 우리는 시간의 복잡도를 정의하고 큰 O 기호를 도입했다.

시간 복잡도는 하나의 함수로 알고리즘의 입력량에 따라 알고리즘에 필요한 시간량을 묘사한다.문외한으로 말하자면, 우리는 시간의 복잡도는 모든 문장이 집행하는 횟수의 합이라고 말할 수 있다.
시간 복잡도는 다음과 같은 세 가지 유형이 있습니다.

일정 시간⇒ O(1) - 입력 크기에 관계없이 실행 시 변경되지 않습니다.

선형 시간⇒ O(n) - "n"입력이 증가함에 따라 실행할 때 선형적으로 증가합니다.

2차 시간⇒ O(n²) - 함수 하나를 완성하는 데 걸리는 시간이 2차 함수처럼 증가합니다.

시간의 복잡성을 더욱 잘 이해하기 위해 몇 가지 코드 예시를 봅시다.

일정 시간 - O(1)

function displayFirstItem(inpArray) {
    console.log(inpArray[0]);
}

위의 함수는 입력에 따라 O(1) 시간 또는 상수 시간 내에 실행됩니다.이것은 입력 그룹이 1항 또는 1000항이 될 수 있음을 의미하지만, 이 함수는 한 번 실행되어 그룹의 첫 번째 항목을 표시합니다.

선형 시간⇒ O（n）

function displayAllItems(inpArray) {
    inpArray.forEach(function(item) {
            console.log(item);
  });
}

상기 함수는 O(n) 시간 (또는 "선형 시간") 으로 실행되며, 여기서 "n"은 그룹의 항수입니다.이것은 수조에 10개의 항목이 있으면 이 함수는 10회 실행된다는 것을 의미한다.1000개의 항목이 있으면 이 함수는 1000번 실행됩니다.

이차 시간⇒ O（n²）

function displayAllPossibleOrderedPairs(inpArray) {
  inpArray.forEach(firstItem => {
    inpArray.forEach(secondItem => {
      console.log(firstItem, secondItem);
    });
  });
}

위의 예에서 두 개의 중첩된 순환이 있다.만약 수조에'n'항목이 있다면, 외순환은'n'번을 실행하고, 내순환은'n'번을 반복해서 실행하며, n²의 총 인쇄수를 얻는다.
따라서 함수는 O(n²) 시간(또는 "2차 시간")으로 실행됩니다.만약 수조에 10개의 항목이 있다면, 이 함수는 100번 실행될 것이다.만약 그것이 1000개의 항목이 있다면, 그것은 1000000번 실행될 것이다.

최악의 경우

최악의 경우 대개 대O표현법으로 논의한다. 왜냐하면 일반적인 상황에서 최악의 경우 운행 시차가 가장 좋은 경우의 운행 시차보다 현저하기 때문이다.

function contains(haystack, needle) {

  // Does the haystack contain the needle?
  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle) {
      return true;
    }
  }

  return false;
}

위의 예에서 건초더미에는 100개의 항목이 있을 수 있지만 첫 번째 항목은 바늘일 수 있다. 이런 상황에서 나는 순환의 1회 교체에서 돌아올 것이다.이 경우 실행 시 O (1) 가 표시됩니다.
그러나 마지막 교체에서 포인터를 찾으면 실행할 때 O(n)가 됩니다.따라서 더욱 구체적으로 말하면 우리는 가장 좋은 상황의 장면은 O(1)가 실행될 때, 가장 나쁜 상황의 장면은 O(n)가 실행될 것이라고 말할 수 있다.

공간 복잡성

공간 복잡도는 하나의 함수로 알고리즘의 입력량에 따라 알고리즘이 차지하는 메모리량(공간)을 설명한다.우리가 "이 알고리즘은 일정한 추가 공간을 필요로 한다"고 말할 때, 필요한 추가 메모리는 처리된 항목 수에 따라 달라지지 않기 때문이다.

그래서 문제는 우리가 언제 집행 속도에 타협할 것인가?간단한 답은 실행 중인 프로그램에 할당할 수 있는 자원의 가용성입니다.
몇 가지 코드 예제를 살펴보겠습니다.

O(1) - 고정 공간(입력 크기 고정용)

function greet(inpArray) { 
 for (let i = 0; i < inpArray.length; i++) {
    console.log('Hello');
  }                                          
}

위의 예시에서 함수는 O(1), 즉 고정 공간을 사용합니다. 입력 그룹의 크기에 변화가 없기 때문에 우리는 컨트롤러에 문자열 하나만 인쇄합니다.

O(n) - 공간 사용량이 선형적으로 증가

function greetNTimes(n) {
  const greetArray = [];
  for (let i = 0; i < n; i++) {
    greetArray[i] = 'Hello';
  }
  return greetArray;
}

상기 함수에서 "n"입력의 크기가 증가함에 따라greetArray의 크기도 증가합니다.이것은 더 큰 진열에 적응하기 위해 추가 메모리 자원을 분배해야 한다.

O(1) - 고정 공간(가변 입력 크기용)

function getLargestItem(items) {
  let largest = -Number.MAX_VALUE;
  items.forEach(item => {
    if (item > largest) {
      largest = item;
    }
  });
  return largest;
}

상기 예시에서'항목'의 크기는 바뀔 수 있지만 메모리 자원의 어떠한 분배도 초래하지 않는다.따라서 이 함수는 입력에 의존하지 않고 고정 공간이나 O(1)를 사용합니다.

결론

그렇다면 어떻게 우리의 코드를 최적화합니까?

코드를 최적화하기 전에 우리는 먼저 최적화 배후의 목표를 이해해야 한다.우리는 일괄 처리 작업의 일부분을 실행하는 코드를 최적화하고 있습니까, 아니면 수천 명의 사용자가 방문하는 실시간으로 사용하는 코드를 최적화하고 있습니까?
이 목표는 매우 중요하다. 왜냐하면 우리는 문제의 대체 해결 방안을 찾을 수 있고 그들의 운행 시간을 비교하여 우리의 목표를 만족시킬 수 있기 때문이다.
비록 일정한 시간 O(1)가 선형 시간 O(n)보다 더 좋을 것 같지만, 코드의 가독성이 충분한지, 코드가 유지 보수하기 쉬운지, 전체적으로 얼마나 많은 메모리를 소모하는지 등 다른 요소를 고려해야 합니다.
나는 네가 이 문장을 좋아하길 바란다.나는 본고가 소프트웨어 개발 분야에 진출하고 싶은 비컴퓨터 과학 졸업생들에게 유익한 지도를 제공할 수 있기를 진심으로 바란다.
너는 트위터에서 나를 팔로우할 수 있다

다음 글도 참조하십시오.