시간 복잡도(Time Complexity)

• 알고리즘 : 문제를 해결하는 최선의 선택
• 효율적인 방법으로 문제를 해결하기 : 시간 복잡도 고려
• 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 의미
• 효율적인 알고리즘 구현 : 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 구성
• 시간 복잡도는 주로 빅-오 표기법을 사용해 표기

  시간 복잡도 표기법

  • Big-O(빅-오) : 최악의 경우를 고려
  • Big-Ω(빅-오메가) : 최선의 경우를 고려
  • Big-θ(빅-세타) : 중간(평균)

1. Big-O 표기법

• 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있음
• 최소한 특정 시간 이상이 걸린다 혹은 이 정도 시간이 걸린다를 고려하는 것보다 이 정도 시간까지 걸릴 수 있다를 고려해야 그에 맞는 대응이 가능
  *최선의 경우만 고려한 경우 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하므로 문제를 파악하는 데 많은 시간이 필요
• 최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 최악의 경우도 고려하여 대비하는 것이 바람직
• Big-O 표기법의 종류 : O(1) > O(logn) > O(n) > O(n^2) > O(2^n) 순서로 빠름

1초가 걸리는 입력의 크기

• O(n) : 100,000,000
• O(n log n) : 5,000,000
• O(n^2) : 10,000
• O(n^3) : 500
• O(2^n) : 26
• O(n!) : 11

1) O(1) : constant complexity

function O_1_algorithm(arr, index) {
  return arr[index]
}

let arr = [1, 2, 3, 4, 5]
// arr의 길이가 100만이라도, 즉시 해당 index에 접근해 값을 반환할 수 있음
let index = 1
let result = O_1_algorithm(arr, index)
console.log(result) 
// 2

• 입력값이 증가하더라도 시간이 늘어나지 않는데, 이는 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있음을 의미
  

2) O(n) : linear complexity

// 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가
function O_n_algorithm(n) {
  for (let i = 0; i < n; i++) {
    // do something for 1 second
  }
}

// 입력값(n)이 1 증가할때마다 코드의 실행 시간이 2초씩 증가
function another_O_n_algorithm(n) {
  for (let i = 0; i < 2n; i++) {
    // do something for 1 second
  }
}

• 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미
• 2n, 5n 을 모두 O(n)이라고 표기
  *입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문
  

3) O(log n) : logarithmic complexity

let i = 4

while(Math.floor(i) > 0) {
 i = i / 2
}

console.log(i) // 0.5

• Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가짐
• 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)
• 이진탐색트리(Binary Search Tree) : 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)
  *원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듬
  

4) O(n^2) : quadratic complexity

// n^2 : 이중반복문
function O_quadratic_algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // do something for 1 second
    }
  }
}

// n^3 : 삼중반복문
function another_O_quadratic_algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        // do something for 1 second
      }
    }
  }
}

• 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미
  *1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 되는 알고리즘의 시간 복잡도
• n^3과 n^5 도 모두 O(n2)로 표기
  *n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문
  

5) O(2^n) : exponential complexity

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

• Big-O 표기법 중 가장 느린 시간 복잡도를 가짐
• 재귀로 구현하는 피보나치 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘
  *n이 100 이상이면 평생 결과를 반환받지 못할 수 있음
  

2. 크롬 개발자 도구에서 함수 실행 시간 측정 방법

var t0 = performance.now()
fib(50) // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now()
console.log("runtime: " + (t1 - t0) + 'ms')

Greedy Algorithm

• Greedy Algorithm(탐욕 알고리즘) : 매 순간 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식
• 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있음

1. 단계적 절차

• 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
• 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
• 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

2. 최적의 해를 보장하지 못하는 특정한 상황

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성
  *위의 2가지 조건을 성립해야 함

Dynamic Programming

• Dynamic Programming(DP) : 동적 계획법
• 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식
  *탐욕 알고리즘과 같이 작은 문제에서부터 출발한다는 점은 같으나 Dynamic Programming은 모든 경우의 수를 조합해 최적의 해법을 찾는다는 점에 차이가 있음

1. 단계적 절차

• 하위 문제를 계산한 뒤 그 해결책을 저장
• 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄임
  *하나의 문제는 단 한 번만 풀도록 하는 알고리즘

2. 사용 조건

• Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견되는 경우
  *큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 함
• Optimal Substructure : 작은 문제에서 구한 최적의 해결 방법(Optimal solution)의 결합으로 그것을 포함하는 큰 문제의 최적의 해법(Optimal solution)을 구할수 있는 경우
  *작은 문제에서 구한 정답을 큰 문제에서도 사용될 수 있어야 함

3. 구현하기

1) Recursion + Memoization으로 구현하기

• 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여, 이 방식을 Top-down 방식이라고도 함

// fibMemo 함수의 파라미터로 n 과 빈 배열을 전달
// 빈 배열은 하위 문제의 결괏값을 저장하는 데에 사용
function fibMemo(n, memo = []) {
  // 이미 해결한 하위 문제인지 찾아본다
  if(memo[n] !== undefined) return memo[n]
  if(n <= 2) return 1
  // 없다면 재귀로 결괏값을 도출하여 res 에 할당
  let res = fibMemo(n-1, memo) + fibMemo(n-2, memo)
  // 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
  memo[n] = res
  return res
}

2) Iteration + Tabulation으로 구현하기

• 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법으로, 이 방식을 Bottom-up 방식이라고도 함

function fibTab(n) {
  if(n <= 2) return 1
  let fibNum = [0, 1, 1]
  // n 이 1 & 2일 때의 값을 미리 배열에 저장
  for(let i = 3; i <= n; i++) {
    fibNum[i] = fibNum[i-1] + fibNum[i-2]
    // n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
    // n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴
  }
  return fibNum[n]
}

구현(Implementation)

• 구현 능력 : 정해진 시간 안에 빠르게 문제를 해결하는 능력
• 구현 문제 : 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것
• 구현 능력을 보는 대표적인 사례 : 완전 탐색(brute force), 시뮬레이션(simulation)

1. 완전 탐색(brute force)

문제 해결을 할 때의 두 가지 규칙

1. 문제를 해결할 수 있는가?
   : 모든 문제는 완전 탐색으로 풀 수 있음
2. 효율적으로 동작하는가?
   : 최의 경우 끝까지 탐색해야 하기에 두 번째 규칙을 만족할 수 없음

• 모든 경우의 수를 탐색하는 모든 경우를 통칭
• 문제를 풀 수 있는 가능한 모든 방법을 고려한 후 효율적으로 동작하는 알고리즘이 전부 탐색할 수밖에 없다고 판단될 때 적용
• 완전 탐색 : Brute Force(무차별 대입), 재귀, 순열, DFS/BFS 등 여러 가지 존재
  *Brute Froce : 조건/반복을 사용하여 해결

2. 시뮬레이션(simulation)

• 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형