Math Algorithms

Fibonacci Sequence

앞의 두 개의 정수를 더한 값이 오는 배열

예를 들어, fibonacci(7) = [0, 1, 1, 2, 3, 5, 8]

가장 첫 값은 [0, 1] 로 시작한다.

function fibonacci(n) {
    const fib = [0, 1];
    for (let i = 2; i < n; i++) {
        fib[i] = fib[i-1] + fib[i-2]
    }
    return fib;
}

 

시간복잡도: O(n) -> for문이 있기 때문에 입력받은 n의 영향을 받게 됨

 

Factorial of a number

입력 받은 숫자보다 작거나 같은 정수를 모두 곱한 것. 0의 팩토리얼은 1

function factorial(n) {
  let ret = 1
  for (let i = 2; i <= n; i++) {
    ret *= i
  }

  return ret
}

factorial(0)

 

시간복잡도: O(n) -> for문이 있기 때문에 입력받은 n의 영향을 받게 됨

 

Prime number

소수 : 주어진 수를 나눌 수 있는 수가 1과 자신밖에 없는 수

function isPrime(n) {
	if (n < 2) return false;
    for(let i = 2; i < n; i++) {
    	if (n % 1 === 0) return false
    }
    return true
}

 

근데 소수인 건 n의 루트값보다 작거나 같은 수만 확인하면 더 빨리 찾을 수 있다.

위와 같은 경우라면 아래처럼 바꿀 수 있고, 이렇게 된다면 Big-O는 O(sqrt(n))

for (let i = 2; i <= Math.sqrt(n); i++) {
	// ... 
}

 

Power of two

2의 제곱인지 아닌지를 확인하는 방법

function powerOfTwo(n) {
  if (n < 1) return false
  while (n > 1) {
    if (n % 2 !== 0) return false
    n = n / 2
  }
  return true
}

 

시간 복잡도는 O(logn) 

 

-> O(1) 복잡도로 확인하기

function powerOfTwo(n) {
  if (n < 1) return false
  return (n & (n - 1)) == 0
}

 

2의 거듭제곱인 수는 이진법으로 바꾸면 2(10), 4(100), 8(1000), 16(10000) 이런 식으로 가고,

거듭제곱에서 1을 뺀 수를 이진법으로 바꾸면 1(1), 3(11), 7(111), 15(1111) 이렇게 가는데

비트 연산자인 & 는 모든 비트가 1일 때 0을 반환한다.

 

그래서 2와 1을 이진법으로 비트연산하면 (11 --> 0 리턴)

4와 3을 하면 (111 --> 0 리턴), 8과 7을 하면 (1111 --> 0 리턴), 16과 15를 하면 (11111 --> 0 리턴)

 

그래서 더 간단하게 2의 거듭제곱인지를 확인할 수 있게 된다.

 

Recursion

재귀함수, 문제를 단순화하기에 좋은 기술이다.

 

주의할 점!

- 모든 재귀는 그 재귀를 끝내는 조건이 있어야 한다. 

- 재귀라고 해서 빠른 방법이 아니다. 단순한 반복문이 더 빠를 때가 많이 있다.

 

피보나치 수열 재귀함수로 만들어보기

반복을 끝내는 base case를 꼭 써주어야 한다.

피보나치 수열은  처음이 차례대로 [0, 1]로 가기 때문에 2보다 작은 경우 그 숫자를 리턴해주면 

그 뒤에 실행되는 함수에서는 그 수를 이용해서 더하기를 하게 된다.

function recursiveF(n) {
  if (n < 2) return n
  return recursiveF(n - 1) + recursiveF(n - 2)
}

 

예를 들어, n이 5라면 (4, 3) => ((3, 2), (2, 1)) => (((2, 1), (1, 0)), ((1, 0), (1, 0))) => ((1, 0), 1, 1, 0, 1, 0, 1) => 5

결국 재귀함수의 경우 함수가 한 번씩 더 탈 때마다 2의 제곱근이 된다. (2, 4, 8 이런 식으로)

 

그러면 재귀함수로 계산을 한 피보나치 수열의 시간 복잡도는 O(2^n)인데 이건 기존 피보나치 수열(O(n))에 비해서 좋지 않음

그래서 피보나치 수열에 대해서 재귀는 좋지 않은 알고리즘임을 알 수 있다. 

 

팩토리얼 재귀함수로 만들어보기

팩토리얼의 base case는 F(0) = 1 이다.

function f(n) {
  if (n === 0) return 1
  return n * f(n - 1);
}

 

 

얘의 Big O는 O(n) 이 된다.