어떻게 자바 스 크 립 트 로 알고리즘 복잡 도 를 학습 합 니까?

개술
본 고 에서 우 리 는'2 차방'과'n log(n)'등 용어 가 알고리즘 에서 의 의 미 를 연구 할 것 이다.
뒤의 예 에서 나 는 이 두 배열 을 인용 할 것 이다.하 나 는 5 개의 요 소 를 포함 하고 다른 하 나 는 50 개의 요 소 를 포함한다.자 바스 크 립 트 에서 편리 한 performance API 를 사용 하여 실행 시간의 차 이 를 평가 할 것 입 니 다.

const smArr = [5, 3, 2, 35, 2];

const bigArr = [5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2];

빅 O 기호 가 뭐 예요?
빅 O 표현법 은 데이터 집합 이 증가 함 에 따라 계산 임무 의 난이도 가 전반적 으로 증가 한 다 는 것 을 나타 내 는 방식 이다.다른 표현법 도 있 지만 보통 빅 O 표현법 이 가장 많이 사용 되 는데 최 악의 상황 에 착안 하여 양 적 이 고 고려 하기 쉽 기 때문이다.최 악의 경 우 는 임 무 를 완성 하 는 데 가장 많은 조작 횟수 가 필요 하 다 는 것 을 의미한다.만약 당신 이 1 초 안에 큐 브 를 어 지 럽 히 는 것 을 회복 할 수 있다 면,당신 은 한 바퀴 만 돌 았 다 면,자신 이 가장 잘 했다 고 말 할 수 없습니다.
알고리즘 을 더 알 게 되면 매우 유용 하 다 는 것 을 알 게 될 것 입 니 다.이러한 관 계 를 이해 하 는 동시에 코드 를 작성 하면 시간 이 어디 에 쓰 였 는 지 알 수 있 기 때 문 입 니 다.
빅 O 표현법 에 대한 정 보 를 더 많이 알 게 되면 다음 그림 에서 다른 변 화 를 볼 수 있다.우 리 는 복잡 도 를 가능 한 한 낮은 수준 으로 유지 하고 O(n)를 초과 하 는 것 을 피 하 는 것 이 좋 겠 다.

O(1)
이것 은 이상 적 인 상황 이다.몇 개의 항목 이 있 든 하나 든 백만 개 든 완 성 된 시간 은 변 하지 않 을 것 이다.단일 작업 을 수행 하 는 대부분의 작업 은 O(1)입 니 다.데 이 터 를 배열 에 쓰 고 특정 색인 에서 항목 을 가 져 오 며 하위 요 소 를 추가 하 는 데 같은 시간 이 걸 립 니 다.이것 은 배열 의 길이 와 무관 합 니 다.

const a1 = performance.now();
smArr.push(27);
const a2 = performance.now();
console.log(`Time: ${a2 - a1}`); // Less than 1 Millisecond


const b1 = performance.now();
bigArr.push(27);
const b2 = performance.now();
console.log(`Time: ${b2 - b1}`); // Less than 1 Millisecond

O(n)
기본 적 인 상황 에서 모든 순환 은 선형 으로 증가 하 는데 데이터 의 크기 와 완 성 된 시간 사이 에 일대일 관계 가 존재 하기 때문이다.그래서 1,000 개의 배열 항목 이 있다 면 1,000 배 는 걸 릴 것 이다.

const a1 = performance.now();
smArr.forEach(item => console.log(item));
const a2 = performance.now();
console.log(`Time: ${a2 - a1}`); // 3 Milliseconds

const b1 = performance.now();
bigArr.forEach(item => console.log(item));
const b2 = performance.now();
console.log(`Time: ${b2 - b1}`); // 13 Milliseconds

O(n^2)
지수 증 가 는 함정 이다.우 리 는 모두 빠 진 적 이 있다.배열 의 모든 항목 에 일치 하 는 것 을 찾 아야 합 니까?순환 을 순환 에 넣 는 것 은 1000 개 항목 의 배열 을 백만 개의 조작 검색 으로 바 꿀 수 있 는 좋 은 방법 입 니 다.이것 은 브 라 우 저 로 하여 금 응답 을 잃 게 할 것 입 니 다.이중 끼 워 넣 기 순환 으로 백만 번 의 조작 을 하 는 것 보다 두 개의 단독 순환 에서 2,000 번 의 조작 을 하 는 것 이 좋다.

const a1 = performance.now();
smArr.forEach(() => {
    arr2.forEach(item => console.log(item));
});
const a2 = performance.now();
console.log(`Time: ${a2 - a1}`); // 8 Milliseconds


const b1 = performance.now();
bigArr.forEach(() => {
    arr2.forEach(item => console.log(item));
});
const b2 = performance.now();
console.log(`Time: ${b2 - b1}`); // 307 Milliseconds

O(log n)
대수 성장 에 대한 가장 좋 은 비 유 는 사전 에서'notation'같은 단 어 를 찾 는 것 을 상상 하 는 것 이 라 고 생각 합 니 다.한 단어 에 한 단어 씩 검색 하지 않 고'N'부분 을 먼저 찾 은 다음'OPQ'페이지 를 찾 은 다음 일치 하 는 항목 을 찾 을 때 까지 알파벳 순 으로 목록 을 검색 합 니 다.
이러한'나 누 어 다스 리 는'방법 을 통 해 어떤 내용 을 찾 는 시간 은 사전 의 크기 에 따라 달라 지지 만 O(n)에 크게 못 미친다.대부분의 데 이 터 를 보지 않 고 더 구체 적 인 부분 을 점차적으로 검색 하기 때문에 천 개의 항목 을 검색 하 는 데 10 개 이상 의 조작 이 필요 할 수도 있 고 100 만 개의 항목 은 20 개 이상 의 조작 이 필요 할 수도 있어 효율 을 극 대화 할 수 있다.
이 예 에서 우 리 는 간단 한 빠 른 정렬 을 할 수 있다.

const sort = arr => {
  if (arr.length < 2) return arr;

  let pivot = arr[0];
  let left = [];
  let right = [];

  for (let i = 1, total = arr.length; i < total; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  };
  return [
    ...sort(left),
    pivot,
    ...sort(right)
  ];
};
sort(smArr); // 0 Milliseconds
sort(bigArr); // 1 Millisecond

O(n!)
최 악의 가능성 은 분석 성장 이다.가장 대표 적 인 예 는 여행 의 판매원 문제 다.만약 당신 이 많은 거리 가 다른 도시 사 이 를 여행 하려 고 한다 면,어떻게 모든 도시 사 이 를 기점 으로 돌아 가 는 가장 짧 은 노선 을 찾 습 니까?폭력 방법 은 모든 도시 간 의 가능 한 노선 거 리 를 검사 하 는 것 이 될 것 이다.이것 은 하나의 단계 이 고 곧 통 제 력 을 잃 을 것 이다.
이 문 제 는 곧 매우 복잡 해 질 것 이기 때문에 우 리 는 간단 한 재 귀 함 수 를 통 해 이러한 복잡성 을 보 여줄 것 이다.이 함 수 는 하나의 숫자 를 함수 자신 에 게 곱 한 후에 숫자 를 1 로 줄인다.곱 하기 중의 모든 숫자 는 0 이 될 때 까지 이렇게 계산 하고 모든 재 귀 층 은 그 곱 하기 를 원시 숫자 에 추가 합 니 다.
단 계 는 1 부터 이 숫자의 곱셈 까지 이다.그럼 6!1x2x3x4x5x 6=720 입 니 다.

const factorial = n => {
  let num = n;

  if (n === 0) return 1
  for (let i = 0; i < n; i++) {
    num = n * factorial(n - 1);
  };

  return num;
};
factorial(1); // 2 Milliseconds
factorial(5); // 3 Milliseconds
factorial(10); // 85 Milliseconds
factorial(12); //  11,942 Milliseconds

나 는 원래 factorial(15)을 표시 하려 고 했 지만 12 이상 의 값 이 너무 많 고 페이지 를 붕괴 시 켰 다.이것 은 왜 이런 상황 을 피해 야 하 는 지 를 증명 했다.
종결 어
우 리 는 고성능 코드 를 작성 해 야 한 다 는 것 은 사실 과 다 를 바 없 는 것 같 지만,나 는 거의 모든 개발 자 들 이 적어도 두 겹,심지어 세 겹 의 플러그 인 순환 을 만 들 었 다 는 것 을 확신한다.왜냐하면 그것 은 확실히 효과 가 있 기 때문이다.빅 오 표현법 은 복잡성 을 표현 하고 고려 하 는 데 필수 적 이 며,이 는 우리 가 가 져 본 적 이 없 는 방식 이다.
이상 은 JavaScript 로 알고리즘 복잡 도 를 어떻게 배 우 는 지 에 대한 상세 한 내용 입 니 다.JS 알고리즘 복잡 도 에 관 한 자 료 는 저희 의 다른 관련 글 에 주목 하 십시오!