⏱️ 시간 복잡도

• Big-O(빅 오) 표기법 알고리즘 최악의 실행 시간을 표기
• 최소한 보장되는 성능을 표기하기 때문에 가장 일반적으로 사용
• Big-O 표기법으로 표현 알고리즘 최상의 실행 시간을 표기

빅오 표기법(big-O notation) 특징

• 시간복잡도에 미미한 영향을 주는 것들은 배제하고 표기

  1. 상수항을 무시

     어떤 알고리즘이 O(N+5)의 복잡도를 가졌으면 상수를 생략해 O(N)으로 표기

  2. 계수도 무시

     어떤 알고리즘이 O(3N)의 복잡도를 가졌으면 계수를 생략해 O(N)으로 표기

  3. 최고차항만 표기

     어떤 알고리즘이 O(3N^3+2N^2+N+5)의 복잡도를 가졌으면 O(N^3)으로 표기

빅오 표기법(big-O notation) 종류

실행 속도 O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N)<O(N!)

O(1) : 상수 시간

• 입력값(N)이 증가해도 실행시간은 동일한 알고리즘, index로 접근하여 바로 처리할 수 있는 연산 과정의 시간 복잡도
• 입력값의 크기와 관계없이 즉시 출력값을 얻을 수 있음
• stack의 push, pop

O(log n) : 로그 시간 복잡도

• 연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘 (log의 지수는 항상 2)
• binary search 알고리즘, tree 형태 자료구조 탐색

function findFruit(fruits, target) {
  let left = 0;
  let right = fruits.length - 1;

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

    if (fruits[mid] === target) {
      return mid; // 과일 찾으면 인덱스 반환
    } else if (fruits[mid] < target) {
      left = mid + 1; // 오른쪽 절반 탐색
    } else {
      right = mid - 1; // 왼쪽 절반 탐색
    }
  }
  return -1; // 과일이 없으면 -1 반환
}

const fruits = ["apple", "banana", "cherry", "grape", "orange"];
console.log(findFruit(fruits, "grape")); // 3 (grape 위치)
console.log(findFruit(fruits, "mango")); // -1 (없음)

O(n) : 선형 복잡도

• 입력값(N)이 증가함에 따라 실행시간도 선형적으로 증가하는 알고리즘
• 1중 for문

function findStudent(students, target) {
  for (let i = 0; i < students.length; i++) {
    if (students[i] === target) {
      return i; // 찾으면 인덱스 반환
    }
  }
  return -1; // 없으면 -1 반환
}

const students = ["John", "Emma", "Liam", "Sophia", "Olivia"];
console.log(findStudent(students, "Liam")); // 2
console.log(findStudent(students, "Lucas")); // -1

O(n log n) : 선형 로그 시간 복잡도

• O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태
• 데이터가 많아질수록 성능이 좋음
• 거의 모든 정렬 알고리즘이 이 복잡도
• 퀵 / 병합 / 힙 정렬

function sortBooks(books) {
  if (books.length <= 1) return books; // 책이 1권이면 그대로 반환

  const mid = Math.floor(books.length / 2);
  const left = sortBooks(books.slice(0, mid)); // 왼쪽 절반 정렬
  const right = sortBooks(books.slice(mid)); // 오른쪽 절반 정렬

  return mergeBooks(left, right);
}

function mergeBooks(left, right) {
  let sorted = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      sorted.push(left[i++]); // 작은 값 먼저 넣기
    } else {
      sorted.push(right[j++]);
    }
  }
  return sorted.concat(left.slice(i), right.slice(j)); // 남은 책 합치기
}

const books = ["Harry Potter", "The Hobbit", "1984", "Moby Dick"];
console.log(sortBooks(books)); // 알파벳순 정렬

O(n^2) : 2차 복잡도 (제곱 시간 복잡도

• O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태
• 2중 For 문, 삽입/거품/선택 정렬

function bubbleSortHeights(heights) {
  for (let i = 0; i < heights.length - 1; i++) {
    for (let j = 0; j < heights.length - i - 1; j++) {
      if (heights[j] > heights[j + 1]) {
        [heights[j], heights[j + 1]] = [heights[j + 1], heights[j]]; // 자리 바꿈
      }
    }
  }
  return heights;
}

const studentHeights = [160, 150, 170, 155, 165];
console.log(bubbleSortHeights(studentHeights)); // [150, 155, 160, 165, 170]

O(2^n) : 지수 시간 복잡도

• 빅오 표기법 중 가장 느린 시간 복잡도로 주로 재귀적으로 수행하는 알고리즘이 이에 해당
• 재귀, fibonacci 수열

// fibonacci(5) → fibonacci(4) + fibonacci(3)
// fibonacci(5) → (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
// 데이터가 많아질수록 시간이 기하급수적으로 증가합니다.
function fibonacci(n) {
  if (n <= 1) return n; // 종료 조건
  return fibonacci(n - 1) + fibonacci(n - 2); // 재귀 호출
}

console.log(fibonacci(5)); // 5 (0, 1, 1, 2, 3, 5)
console.log(fibonacci(7)); // 13

O(n!) : 팩토리얼 시간 복잡도

• 순열, 조합 알고리즘

function seatFriends(friends) {
  if (friends.length === 0) return [[]]; // 빈 리스트면 빈 배열 반환

  let results = [];
  for (let i = 0; i < friends.length; i++) {
    let remaining = friends.slice(0, i).concat(friends.slice(i + 1)); // 현재 친구 제외
    let perms = seatFriends(remaining); // 남은 친구들을 재귀적으로 자리 배치

    for (let perm of perms) {
      results.push([friends[i], ...perm]); // 현재 친구 + 나머지 조합
    }
  }
  return results;
}

const friends = ["Alice", "Bob", "Charlie"];
console.log(seatFriends(friends)); 
// [['Alice', 'Bob', 'Charlie'], ['Alice', 'Charlie', 'Bob'], ['Bob', 'Alice', 'Charlie'], ...]

데이터 크기에 따른 시간복잡도

데이터 크기 제한	예상되는시간 복잡도
n ≤ 1,000,000	O(n) or O (logn)
n ≤ 10,000	O(n2)
n ≤ 500	O(n3)

🛖 공간복잡도

• 알고리즘이 실행될 때 사용되는 메모리의 양을 나타냄
• 주어진 입력에 대해 알고리즘이 얼마나 많은 추가 공간을 필요로 하는지를 나타냄
• Big-O 표기법으로 표현

O(1) : 상수 공간 복잡도

• 입력 크기와 관계없이 고정된 양의 메모리만 사용
• 기본적인 변수 저장, 단순한 연산을 위한 메모리 할당

function getFirstElement(arr) {
  return arr[0]; // 배열의 첫 번째 요소만 반환
}

O(n) : 선형 공간 복잡도

• 입력 크기 N에 비례하는 양의 메모리를 사용
• 배열, 리스트 등에서 각 요소를 저장할 때

function duplicateArray(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr.push(arr[i]);
  }
  return newArr;
}

O(n^2) : 2차원 공간 복잡도

• 이차원 배열이나 행렬과 같이 2D 데이터를 처리할 때 사용
• 2D 배열을 다룰 때

function createMatrix(n) {
  let matrix = [];
  for (let i = 0; i < n; i++) {
    let row = [];
    for (let j = 0; j < n; j++) {
      row.push(0);
    }
    matrix.push(row);
  }
  return matrix;
}

O(log n) : 로그 공간 복잡도

• 재귀 알고리즘에서 호출 스택의 깊이가 로그에 비례할 때 발생
• 이진 탐색

function binarySearch(arr, target) {
  function search(left, right) {
    if (left > right) return -1;
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) return search(mid + 1, right);
    return search(left, mid - 1);
  }

  return search(0, arr.length - 1);
}

O(n!) : 팩토리얼 공간 복잡도

• 순열, 조합을 생성할 때 발생하는 공간 복잡도
• 순열 생성 알고리즘

function generatePermutations(arr) {
  if (arr.length === 0) return [[]];
  let result = [];
  for (let i = 0; i < arr.length; i++) {
    let rest = arr.slice(0, i).concat(arr.slice(i + 1));
    let perms = generatePermutations(rest);
    for (let perm of perms) {
      result.push([arr[i], ...perm]);
    }
  }
  return result;
}

데이터 크기에 따른 공간 복잡도

데이터 크기 제한	예상되는 공간 복잡도
n ≤ 1,000,000	O(1) 또는 O(n)
n ≤ 10,000	O(n^2)
n ≤ 500	O(n^3)

시간 복잡도 vs. 공간 복잡도

알고리즘 복잡도	시간 복잡도	공간 복잡도
O(1)	입력 크기와 관계없이 일정한 시간	일정한 메모리 사용
O(log n)	입력 크기에 비례하는 로그 시간	재귀 호출 시 스택 깊이에 따라 O(log n)
O(n)	선형적으로 증가하는 시간	선형적인 공간 사용
O(n log n)	로그와 선형 복잡도가 결합된 시간	추가적인 공간이 필요
O(n^2)	이차원 배열 또는 중첩된 루프에서 발생	이차원 배열 사용 시 O(n^2)
O(2^n)	재귀적 방식에서 지수 시간 복잡도	재귀 깊이와 메모리 사용