핵심요약.

테이블 조회 및 수학에 O(1) 연결

O(n)은 목록 순회용임

이상한 로그는 정렬을 위한 것입니다: O(nlogn)

중첩 루프로 O(n2) 연결

화이트보드 인터뷰와 알고리즘 질문에 동의하든 그렇지 않든, 이것에 능숙해지는 것은 어느 시점에서 마스터해야 하는 또 다른 기술입니다. 그리고 알고리즘에 능숙해지려면 BigO의 개념을 파악해야 합니다. 내가 "마스터"가 아니라 "잡다"라고 썼다는 것을 주목하십시오. 이 주제에 대해 신비한 것은 없습니다.

BigO는 단순히 입력 크기가 커짐에 따라 알고리즘의 성능이 얼마나 좋은지 또는 나쁜지를 알려주는 표기법입니다. 알고리즘을 풀고 분석하기 위해 때때로 사용하는 몇 가지 트릭을 확인했습니다.

I sent this post weeks ago to +450 devs on my maillist. Join here if you want to get my tips and thoughts on career growth.

1. 테이블 조회 및 수학에 O(1) 연결

알고리즘은 입력 크기에 관계없이 거의 동일한 시간이 소요됨을 의미합니다. 일반적으로 수학 연산 및 개체 조회에 적용됩니다.

// regardless of a or b, a sum is a math operation that takes just 
// one clock cycle to complete
const add = (a, b) => a + b;

// no matter of how big your map is (e.g an object in JavaScript), 
// a lookup will take 1 cycle to complete
const lookup = (map, key) => map[key];

bar와 같이 foo 객체에서 foo.bar 소품에 액세스할 때를 아십니까? 음, 그것은 O(1) 작업입니다.

참고: 충돌을 해결하는 방법에 관계없이 해시맵 조회는 이론적으로 O(1)로 간주됩니다.

2. O(n)은 목록 순회용입니다.

알고리즘 실행 시간이 입력에 따라 선형적으로 증가함을 의미합니다. 예를 들어, 목록의 최대 수를 찾는 알고리즘을 생각해 보십시오. 어떤 숫자가 최대인지 알기 위해 알고리즘은 반드시 모든 요소를 ​​방문해야 합니다. 목록이 2배 커지면 알고리즘을 완료하는 데 대략 두 배의 시간이 걸립니다.

// you need to loop through all the elements to find the max.
function findMax(list) {
  let max = -Infinity;
  for (obj of list) {
    if (obj > max) max = obj
  }
}

3. 정렬을 위한 이상한 로그: O(nlogn)

이것은 보기보다 쉽습니다. 저기 있는 이상한 로그에 대해 걱정하지 마세요. Logs in BigO 표기법은 일반적으로 무언가를 반으로 나누고 각 반은 다시 반으로 나뉜다는 것을 의미합니다. 그러나 기억해야 할 유일한 것은 O(nlogn)은 대부분 정렬과 관련이 있다는 것입니다. 목록 정렬은 무료 작업이 아니며 사용 시 비용이 발생합니다. 목록의 최대값을 얻는 매우 비효율적인 방법의 예를 살펴보겠습니다.

function getMax(list) {
  return list.sort((a, b) => b - a)[0]
}

O(n)은 O(nlogn)보다 낫습니다. 🦄에 logn을 곱하면 더 큰 🦄이 나오니까요.

이제 최대값을 찾는 데 가장 효율적인 것이 무엇인지 결정할 수 있는 좋은 기준이 있습니다. O(n)을 사용하시겠습니까? 또는 O(nlogn) 알고리즘?

4. 중첩 루프로 O(n2) 연결

입력 크기가 미친 듯이 알고리즘에 영향을 미친다는 것을 의미합니다(다른 것만큼 나쁘지는 않음). 입력 크기가 두 배가 되면 실행 시간이 4배 증가합니다. 입력이 4배 증가하면 실행 시간이 16배 증가합니다. 이것은 일반적으로 중첩된 루프의 모양을 취합니다. 배열에 중복이 있는지 확인하는 매우 비효율적인 방법을 작성해 봅시다.

function hasDuplicates(list) {
  for (let [i, el_i] of list.entries()) {
    for (let [j, el_j] of list.entries()) {
      if (i !== j && el_i === el_j) return true;
    }
  }
  return false;
}

크기 n의 목록에 있는 모든 요소에 대해 크기 n의 전체 목록을 반복합니다. 이는 n*n = n2번 요소를 방문한다는 의미입니다.

이 작업에 대한 O(n) 알고리즘을 생각해낼 수 있습니까? 목록을 한 번만 반복하는 것? 댓글로 알려주세요

요약

학습 알고리즘에 반대한다면 이 주제를 파헤칠 필요가 없습니다. 저는 그것을 존중할 수 있습니다. 이 표를 저장하고 일부 작업은 다른 작업보다 비용이 더 많이 든다는 사실과 그 이유를 알아두세요.

기타

이 주제에는 모든 종류의 complexities and nuances이 있습니다. 을(를) 유지하는 것은 자유입니다. 그러나이 4 가지 개념을 파악하고 마음에 새길 수 있다면 인터뷰, PR 검토 또는 더 나은 코드 작성을 위해 알고리즘 게임의 수준을 높일 수 있습니다.

코딩 인터뷰를 두려워하지 마세요

저는 코딩 알고리즘을 더 잘하기 위해 이러한 개념을 사용했습니다. 그 이후로 AmazonToptal 및 . 나는 원격 기술 인터뷰를 에이스하기 위한 많은 팁과 요령이 있는 FREE guide을 썼습니다. 궁금하시면 sign up here 제 다음 이메일로 받아보실 수 있습니다.




내 DM은 경력, 알고리즘 인터뷰 또는 성장 팁에 대해 항상 열려 있습니다. 나에게 메시지를 보내거나 그냥 인사!