[Node 7기] 알고리즘 강의 - 3일차 시간복잡도, 공간 복잡도, 링크드리스

시간 복잡도

: 최악의 상황을 가정하고 코드 실행할 때 걸리는 시간

 

컴퓨터 과학에서 알고리즘의 시간 복잡도란, 알고리즘이 실행되는 데 걸리는 시간을 입력 크기의 함수로 표현한 것입니다. 복잡한 정의보다, 간단한 사례로 이해하는 게 더 효과적입니다. 

 

사례 1: 

function find_max_num(array) {
    for (let num of array) {
        let isMax = true;
        for (let compare_num of array) {
            if (num < compare_num) {
                isMax = false;
                break;
            }
        }
        if (isMax) {
            return num;
        }
    }
}
console.log("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]));
console.log("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]));
console.log("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]));

 

시간 복잡도 계산:

• 외부 for 루프: 배열의 길이만큼 반복 (N번)
• 내부 for 루프: 배열의 길이만큼 반복 (N번)
• 각 내부 루프에서 실행되는 비교 연산: 1번
• 전체 실행 횟수: N × N = N²

따라서, 이 함수의 시간 복잡도는 O(N²) 입니다.

 

사례 2

function find_max_num(array) {
    let max_num = array[0];
    for (let num of array) {
        if (num > max_num) {
            max_num = num;
        }
    }
    return max_num;
}
console.log("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]));
console.log("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]));
console.log("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]));

시간 복잡도 계산:

• 초기 대입 연산: 1번
• for 루프: 배열의 길이만큼 반복 (N번)
  • 비교 연산: N번
  • 조건 만족 시 대입 연산: 최대 N번
• 전체 실행 횟수: 1 + 2N

빅오 표기법에서는 가장 중요한 N의 지수만 남기고 나머지는 생략합니다.
따라서, 이 함수의 시간 복잡도는 O(N) 입니다.

 

---

공간 복잡도

• 공간 복잡도는 알고리즘이 실행되면서 사용하는 메모리 공간의 양을 나타냄.
• 즉, 입력 크기(예: N)에 따라 얼마나 많은 메모리를 사용하는지를 측정하는 것.
• 메모리 제약이 큰 환경에서는 반드시 고려해야 합니다.
  • 공간 최적화는 경우에 따라 속도를 희생할 수도 있습니다.
• 현업에서는 시간과 공간을 적절히 트레이드오프하며 설계하는 것이 핵심입니다.
• 필요하다면 공간을 더 사용해서 성능을 올리는 것도 좋은 선택입니다.

function largest_product(my_list) {
    let products = [];
    for (let a of my_list) {
        for (let b of my_list) {
            products.push(a * b); // a * b의 결과를 products 배열에 추가
        }
    }
    return Math.max(...products); // products 배열에서 최댓값 반환
}

let myList = [1, 3, 5, 7, 9];
console.log(largest_product(myList));

 

1. 입력 크기: my_list의 길이 = N
2. 사용된 공간:
   • products 배열은 N × N = N² 개의 요소를 저장
   • 그 외에 a, b 같은 임시 변수는 공간 사용량에 거의 영향을 주지 않음
3. 결론: 공간 복잡도는 O(N²)

---

배열

배열은 프로그래밍에서 관련된 데이터를 효율적으로 관리하기 위해 사용하는 기본 자료구조입니다. 

 

배열의 특징

배열: 데이터를 자주 조회할 때 사용

1. 연속된 메모리 공간
   대부분의 언어에서 배열은 연속된 메모리 공간에 저장됩니다. 이를 통해 인덱스를 사용한 빠른 접근이 가능합니다.
   하지만 JavaScript는 예외로, 배열이 객체로 구현되어 있으며, 요소가 반드시 연속된 메모리 공간에 저장되지 않습니다.
2. JavaScript 배열의 특성
   • 동적 타입 언어이기 때문에 배열의 요소 타입이 다양할 수 있습니다.
   • 배열의 크기도 유동적으로 조정 가능하며, Sparse Array(희소 배열)를 지원합니다.
   • 이러한 특성으로 인해 성능은 일반 배열과 다르게 동작할 수 있습니다.

 

배열의 주요 기능

1. 조회
   • 인덱스를 통한 값 접근은 O(1)의 시간 복잡도를 가집니다.
     예) arr[2]는 즉시 값을 반환.
2. 삽입 & 삭제
   • 배열 끝에서의 추가/삭제는 O(1).
   • 배열 중간의 삽입/삭제는 다른 요소들의 재배치가 필요하므로 O(n).
     • 예) [1, 2, 3, 4, 5]에서 인덱스 2에 7 추가:
       • [1, 2, 7, 3, 4, 5] (3~5 재배치 발생)
3. 정렬
   • 사용 알고리즘에 따라 시간 복잡도가 다릅니다.
     • Quick Sort: 평균 O(n log n), 최악 O(n²).
4. 검색
   • 정렬되지 않은 배열: O(n) (모든 요소를 확인)
   • 정렬된 배열: O(log n) (이진 탐색 가능)

---

링크드리스트

 

유동적으로 연결고리를 떼었다가 붙였다가 할 수 있는 자료구조를 링크드리스트라고 합니다

링크드리스트는 데이터 삽입과 삭제에 강점을 가진 자료구조입니다.

링크드리스트: 데이터를 자주 삽입/삭제할 때 사용

 

이를 이해하기 쉽게 화물 열차를 비유

1. 링크드리스트 기본 개념

• 노드(Node): 화물 칸 하나하나가 노드입니다. 각 노드는 데이터를 가지고 있으며, 다음 노드를 가리키는 포인터를 포함합니다.
• 헤드(Head): 첫 번째 노드를 가리킵니다.
• 테일(Tail): 마지막 노드를 가리킵니다. (다음 노드가 없으면 null로 끝냄)
• 포인터: 각 노드는 다음 노드를 가리키는 포인터를 가지고 있습니다.

2. 링크드리스트의 특징

• 추가/삭제: 새로운 노드를 삽입하거나 기존 노드를 삭제할 때 매우 효율적입니다. 예를 들어, "자갈" 칸과 "밀가루" 칸 사이에 "흑연" 칸을 삽입하려면, "자갈" 칸의 포인터를 "흑연" 칸으로 바꾸고, "흑연" 칸의 포인터를 "밀가루" 칸으로 바꾸면 됩니다.
• 조회: 특정 노드를 찾기 위해서는 처음부터 끝까지 노드를 하나씩 순차적으로 방문해야 하므로 조회 성능이 느립니다. 이는 O(N) 시간이 걸립니다.

3. 링크드리스트 구현 예시 (JavaScript)

class Node {
  constructor(data) {
    this.data = data;  // 데이터 저장
    this.next = null;   // 다음 노드를 가리킬 포인터
  }
}

class LinkedList {
  constructor(value) {
    this.head = new Node(value);  // 첫 번째 노드
  }

  // 끝에 노드 추가
  append(value) {
    let curr = this.head;
    while (curr.next !== null) {
      curr = curr.next;  // 끝까지 이동
    }
    curr.next = new Node(value);  // 새로운 노드 연결
  }

  // 특정 인덱스의 노드 반환
  getNode(index) {
    let node = this.head;
    for (let i = 0; i < index; i++) {
      node = node.next;
    }
    return node;
  }

  // 특정 인덱스에 노드 추가
  addNode(index, value) {
    const newNode = new Node(value);
    if (index === 0) {
      newNode.next = this.head;
      this.head = newNode;
      return;
    }
    const node = this.getNode(index - 1);
    const nextNode = node.next;
    node.next = newNode;
    newNode.next = nextNode;
  }
}