JavaScript 알고리즘 & 자료구조 마스터클래스 1

udemy JavaScript 알고리즘 & 자료구조 마스터클래스

big O Notation 빅오 표기법

  • 입력의 크기와 실행시간의 관계

  • 가장 높은 실행 시간을 의미

  • 빅오 표기법에서 상수는 중요하지 않음

속도(시간 복잡도) 메모리사용(공간 복잡도) 읽기 쉬운 코드

1. 시간 복잡도(속도)

function addUpToFirst(n) {
  let total = 0;
  for (let i=1; i<=n; i++) {
    total += i;
  }
  return total;
}
// O(n)

function addUpToSecond(n) {
  return n * (n+1) / 2;
}
// O(1)

console.log(addUpToFirst(6));
console.log(addUpToSecond(6));

// 1.실행 시간의 비교

let t1 = performance.now();
// 브라우저가 이 문서를 만든 시간, 이 창이 열린 시간을 알려줌
addUpToFirst(100000000);
let t2 = performance.now();
console.log(`Time Elapsed: ${(t2-t1) / 1000} seconds.`);
// 완전히 신뢰할 수 없는 방식
// 기계마다 사양에 따라 다름
// 같은 기계여도 다른 타임이 기록 됨
// 너무 빠른 알고리즘의 속도 차이를 측정하기 힘듬

// 2. 컴퓨터가 처리해야하는 연산(operation) 갯수 카운팅
// - 정확한 연산 갯수는 중요치 않음, 전체적인 추세가 중요
// - Performence Tracker

function countUpAndDown(n) {
console.log("Going up!");
for (let i = 0; i < n; i++) {
console.log(i);
}
// O(n)
console.log("At the top!\nGoing down...");
for (let j = n; j >= 0; j--) {
console.log(j);
}
// O(n)
console.log("Back down. Bye!");
}
// O(n)

function printAllPairs(n) {
for (var i = 0; i<n; i++) {
for (var J = 0; j < n; j++) {
console.log(i,j);
}
// O(n)
}
// O(n)
}
// O(n\*n) 중첩되어 있으면 제곱

2. 공간 복잡도(메모리)

배열과 오브젝트의 성능 평가

Objects

  • 객체는 정렬이 필요없을 때 사용

  • 빠른 접근, 입력과 제거를 원할 때 좋음

  • 정렬은 되어 있지 않지만 다른 것들은 매우 빠름

big O of Objects

  • insertion = O(1)

  • Removal = O(1)

  • Searching = O(n)

  • Access = O(1)

big O of Object Mehtods

  • Object.keys = O(n)

  • Object.values = O(n)

  • Object.entries = O(n)

  • hasOwnProperty = O(1)

Arrays

  • 정렬된 리스트, 정렬이 필요할 때 사용

  • 인덱스가 있음

big O of Arrays

  • Insertion = It depends / 어디에 입력하는지에 따라 다름 맨 뒤에 push() = O(1), 맨 앞에 = O(n)

  • Removal = It depends / 어디에 있는 것을 제거하는 지에 따라 다름

  • Searching = O(n)

  • Access = O(1) / 인덱스가 있기 때문

big O of Array Operations

  • push = O(1)

  • pop = O(1)

  • shift = O(n)

  • unshift = O(n)

  • concat = O(n)

  • slice = O(n)

  • splice = O(n)

  • sort = O(n*log n)

  • forEach/map/filter/reduce/etc. = O(n)

Algorithm

문제 해결 접근법

  1. 문제의 이해

    • 문제 자체에 대한 이해

  2. 구체적 예시

    • 입/출력값, 에러, 입력오류, 예외 등

  3. 세부 분석

    • 의사코드, 또는 주석

  4. 해결 또는 단순화

    • 실제 코드 작성, 해결할 수 있는 부분부터 처리

  5. 되돌아 보기와 리팩터 Refactor

    • 리팩토링

PreviousJavaScript 알고리즘 & 자료구조 마스터클래스NextReact

Last updated