21-03-08 자바스크립트로 하는 자료구조와 알고리즘(1)

1장 빅오 표기법

O(1)은 신성하다 - 하미드 티주쉬

빅오 표기법 기초
- 빅오 표기법에서 n은 입력의 개수를 나타낸다
- “n이 무한으로 접근할 때 무슨 일이 일어날까?”
  일반적인 빅오 복잡도 그래프
계수 법칙 : “상수를 제거하라”

상수 k > 0인 경우 f(n)이 O(g(n)이면 kf(n)은 O(g(n))이다**

function Coefficient(n) {
  let count = 0;
  for (let i = 0; i < n; i++) count += 1
  return count;
}
// Coefficient(n)의 복잡도는 O(n)

합의 법칙 : “빅오를 더하라”

f(n)이 O(h(n))이고 g(n)이 O(p(n))이라면 f(n)+g(n)은 O(h(n)+p(n))이다**

function SumBigO(n) {
  let count = 0;
  for (let i = 0; i < n; i++) count += 1;
  for (let i = 0; i < 5*n; i++) count += 1;
  return count;
}
// SumBigO(n)의 복잡도는 O(n + 5n) = O(n)이 된다

곱의 법칙 : “빅오를 곱하라”

f(n)이 O(h(n))이고 g(n)이 O(p(n))이라면 f(n)g(n)은 O(h(n)p(n))이다**

function MultipleBigO(n) {
  let count = 0;
  for (let i = 0; i < n; i++) { 
    count += 1;
    for (let i = 0; i < 5*n; i++) 
      count += 1;
  }
  return count;
}
// MultipleBigO(n)의 복잡도는 O(n^2)

다항 법칙 : “빅오의 k승”

f(n)이 k차 다항식이라면 f(n)은 O(n^k)이다**

function PolynomialBigO(n) {
  let count = 0;
  for (let i = 0; i < n*n; i++) { 
    count += 1;

  }
  return count;
}
// PolynomialBigO(n)의 복잡도는 O(n^2)

2장 자바스크립트의 독특한 특징

자바스크립트는 동적 인터프리터 프로그래밍 언어이기 때문에 다른 객체지향 프로그래밍 언어들과는 구문이 다름

자바스크립트의 범위(scope)

전역 선언: 전역 범위
→ 전역 선언은 안좋은 방법이므로 되도록 사용하지 말 것

var를 사용해 선언 : 함수 범위
→ var를 사용하면 변수를 어디에 선언하더라도 함수의 맨 앞으로 이동한다
→ 이를 변수 호이스팅(variable hoisting)이라고도 한다

function scope1() {
  var top = "top"
  bottom = "bottom";
  console.log(bottom)

  var bottom;
} 
// bottom은 맨 마지막에 선언되었지만 
// console.log() 앞으로 hoisting되며 오류 없이 실행된다

var로 선언된 해당 변수의 범위가 가장 가까운 함수 범위가 된다

function scope2(print) {
  if (print) {
    var insideIf = '12';
  }
  console.log(insideIf);
}
scope2(true);

function scope2_copy(print) {
  var insideIf;
  if (print) {
    insideIf = '12';
  }
  console.log(insideIf);
}
scope2_copy(true);
// scope2와 scope2_copy는 동일하게 실행된다

let를 사용해 선언 : 블록 범위
→ 변수가 선언된 블록 범위({})내에서 유효하다

function scope3(print) {
  if(print) {
    let insideIf = '12'
  }
  console.log(insideIf);
}
scope3(true);
// 오류가 발생함 let은 블록 범위에서만 유효하기 때문에
// if문을 벗어나면 해당 변수를 읽을 수 없다

등가와 형

자바스크립트에는 boolean, number, string, undefined, object, function, symbol과 같은 일곱가지의 기본 자료형이 존재함
값이 선언만 되고 값이 할당되지 않으면 undefined가 됨
타 언어에서 대개 if문 내 매개변수는 boolean형이어야 하지만 자바스크립트에서는 해당 변수가 비었거나 null이거나 undefined라면 false로 평가된다
false로 인식되는 값은 false 외에 0, ‘’(혹은 “”), NaN, undefined, null가 있고 0이 아닌 숫자, 비어있지 않은 문자열이나 객체를 true로 평가한다
자바스크립트는 스크립트 언어이기 때문에 코드가 실행될 때 해당 변수의 형이 해석된다
==는 값만 확인하지만 ===는 형과 값을 모두 확인 한다
"5" == 5 // true vs "5" === 5 // false

자바스크립트에서 동일한 속성과 값을 갖는 두 객체가 동일한지 확인하고자 ==를 사용한다면 변수의 메모리 주소가 다르기 때문에 false를 리턴할 것이다

function isEquivalent(a,b) {
  var aProps = Object.getOwnPropertyNames(a);
  var bProps = Object.getOwnPropertyNames(b);

  // 길이가 다르다면 두 객체는 다른 객체임
  if (aProps.length != bProps.length) return false
  for (var i = 0; i < aProps.length; i++) {
    var propName = aProps[i];

      // 속성값이 다른 경우 두 객체는 같지 않다
      if(a[propName] !== b[propName]) return false
  }

  return true;
}
isEquivalent({'hi':12},{'hi':12}); // true

21-03-08 자바스크립트로 하는 자료구조와 알고리즘(1)

1장 빅오 표기법

2장 자바스크립트의 독특한 특징

Harry Kim