알고리즘 - Big O notation

Big O notation

why is Big O notation neccessary?

• 다른 접근 방법들을 비교했을 때, 어떤 방법이 더 나은지 알기 위해서
• 코드가 느리거나 충돌 났을 때, 비효율적(긴 소요시간/ 많은 메모리 사용) 코드를 찾기 위해서

N : the number of simple operations the computer has to perform
(소요시간은 수행되어야 하는 연산 수에 의해 결정됨)

Big O notation

• 연산 수 n와 런타임의 상관관계를 O(f(n))으로 나타냄
  • f(n) = n : 연산 수가 n일 때 런타임 n 시간 걸림
  • f(n) = n^2 : 연산 수가 n일 때 런타임 n^2 시간 걸림
  • f(n) = 1 : 연산 수가 n일 때 런타임 상수 시간 걸림
  • f(n) = log(n) | nlog(n) : 연산수가 n일 때 런타임이 로그 시간 걸림

• big O notation
  • O(1) : 연산 수와 상관 없이 항상 일정한 시간이 걸림
  • O(N) : 연산 수 N에 비례하여 시간이 늘어남 (loop 문)
  • O(N^2) : 연산 수의 N 제곱에 비례하여 시간이 늘어남 (nested loop 문)
  • O(log(N)) | O(Nlog(N)) : 로그N에 비례하여 시간이 늘어남 (search, sort 알고리즘)

Simplifying Big O Expressions

• 상수는 신경쓰지 않음
  • O(2n) => O(n)
  • O(500) => O(1)
  • O(13n^2) => O(n^2)
• 작은 값은 신경쓰지 않음
  • O(n + 10) => O(n)
  • O(1000n + 50) => O(n)
  • O(n^2 + 5n + 8) => O(n^2)

Big O Shorthands

1. 사칙 연산은 O(1)임
2. 변수 할당은 O(1)임
3. 배열이나 객체의 요소에 접근하는 것은 O(N)임
4. loop 안에서의 복잡도는 복잡도 * loop 길이임

Space Complexity

• time complexity : input 크기가 증가함에 따라 알고리즘의 런타임 소요 시간
• space complexity : 알고리즘 코드를 실행시키기 위해서 할당되어야 하는 메모리 크기
• auxiliary space complexity :input에 의해 차지되는 공간을 제외하고 알고리즘에서 요구되는 공간 복잡도

Space Complexity in JavaScript

• primitive Type (boolean, number, undefined, null)은 O(1) 공간을 필요로 함
• string은 O(n) 공간을 필요로 함 (n: string의 길이)
• Reference Type (array, object)는 O(n) 공간을 필요로 함 (n: array의 길이, object의 key 개수)

Logarithms

• logarithms time complexity는 효율적임
  • O(1) < O(log(N)) < O(N)
  • O(N) < O(Nlog(N)) < O(N^2)
• 특정 search 알고리즘이 logarithmic time complexity를 가짐
• 효율적인 sort 알고리즘이 loagrithms를 포함함
• recursion는 때때로 logarithmic space complexity를 가짐