알고리즘 - 시간 복잡도

  1. 각 코드 블록의 시간 복잡도를 개별적으로 계산한다.

  2. 반복문과 재귀 호출의 시간 복잡도를 분석한다.

  3. 중첩 반복문의 경우 각 반복문의 시간 복잡도를 곱한다.

  4. 조건문은 실행되는 부분만 고려한다.

  5. 함수 호출의 경우 해당 함수의 시간 복잡도를 고려한다.

function sumArray(arr) {
  let sum = 0
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i]
  }
  return sum
}
// 시간 복잡도: O(n)

// 설명: 배열의 길이에 비례하여 한 번의 반복문을 실행한다.
// 각 반복에서 상수 시간 작업을 수행하므로, 전체 시간 복잡도는 O(n)이다.

function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j])
    }
  }
}
// 시간 복잡도: O(n^2)

// 설명: 두 개의 중첩된 반복문이 있으며, 각 반복문은 배열의 길이만큼 반복된다.
// 따라서 전체 시간 복잡도는 O(n) * O(n) = O(n^2)이다.

function findMax(arr) {
  let max = arr[0]
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i]
    }
  }
  return max
}
// 시간 복잡도: O(n)

// 설명: 배열의 길이 n에 비례하여 한 번의 반복문을 실행하며,
// 각 반복에서 상수 시간 작업(비교 및 할당)을 수행한다.
// 따라서 전체 시간 복잡도는 O(n)이다.

function multiplyArray(arr) {
  function multiply(a, b) {
    return a * b
  }

  let result = 1
  for (let i = 0; i < arr.length; i++) {
    result = multiply(result, arr[i])
  }
  return result
}
// multiply 함수: O(1)
// multiplyArray 함수: O(n)

// 설명: multiply 함수는 상수 시간 O(1)을 가지며,
// multiplyArray 함수는 배열의 길이 n에 비례하여 반복문을 실행한다.
// 각 반복에서 상수 시간 작업(함수 호출 및 곱셈)을 수행하므로, 전체 시간 복잡도는 O(n)이다.

function factorial(n) {
  if (n === 0) {
    return 1
  } else {
    return n * factorial(n - 1)
  }
}
// 시간 복잡도: O(n)

// 설명: 재귀 함수는 입력 크기 n에 비례하여 한 번씩 호출된다.
// 각 호출에서 상수 시간 작업(곱셈)을 수행하므로, 전체 시간 복잡도는 O(n)이다.

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)

    if (arr[mid] === target) {
      return mid // O(1)
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return -1 // O(1)
}
// 시간 복잡도: O(log n)

// 이진탐색을 가져온건데,
// let mid = Math.floor((left + right) / 2) - 전체 배열의 가운데에 있는 애 인덱스를 가져온다.
// 그 다음 가운데 있는애가 타겟이면 걔를 정답으로 주고, 타겟보다 작거나 크면 mid에 1을 더하고 빼서 다시 검색한다.
// 찾을때 까지 반복한다.

// 첫 번째 절반 줄이기: n -> n/2
// 두 번째 절반 줄이기: n/2 -> n/4
// 세 번째 절반 줄이기: n/4 -> n/8

// 이런식으로 계속 절반씩 줄여가면서 진행이 될텐데, 이걸 k번 동안 반복한다고 가정하면,
// 처음 줄인거는 n/2 두번째는 n/4 니까, k번째는 n/2^k 이다.

// 검색범위가 1이 되는 시점이 탐색이 종료되는 시점이니까, n/2^k = 1이 된다.
// 분모를 제거하면, n = 2^k가 되고, 결국 몇번 반복하는지가 시간복잡도와 관련이 있으니까
// k의 값을 구하자면

// k = log2^n이 된다.

// 이렇게 이진탐색은 O(log n)이 된다.