Big O Notation

What does better mean?

1. Faster?

2. Less memory-intensive?

3. More readable?

 

The Problem with Time

1. Different machines will record different times

2. The same machine will record different times

 

다른 performance 측정법

Counting Operations이 있지만 연산자를 세는 방법은

힘들고 시간이 오래 걸린다.

 

Big O 정의

간단한 연산들은 컴퓨터가 최대 f(n)번 해야한다면 알고리즘은 O(f(n))이다.

f(n)은 상수형, 선형 등 형태가 다양하다.

 

1. f(n)이 2n일 때 상수는 무시되고 O(n)이 된다.

2. f(n)의 최고차항만 남긴다.

 

O(1)

O(n)과 같이 보이지만 i가 10 이후부터 연산 개수가 증가하지 않기 때문에 O(1)이다!!

function logAtMost10(n) {
  for (var i = 1; i <= Math.min(n, 10); i++) {
    console.log(i);
  }
}

 

Space Complexity

boolean, number, undefined, null은 상수이다.

String 공간 복잡도는 O(n)이다.

참조형은 일반적으로 O(n)이고 n은 배열 길이나 object key 개수이다.