자바스크립트 자료구조 Ⅰ

young-gue Park·2023년 1월 12일

JavaScript 배열 시간복잡도 연결리스트 자료구조

JavaScript

목록 보기

4/20

⚡ 자바스크립트로 보는 자료구조 Ⅰ

📌 자료구조란?

일차원인 컴퓨터 메모리를 현실에 대응되도록 구조를 만든 것
메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표
상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다.
종류
① 단순 구조: 정수, 실수, 문자열, 논리
② 선형 구조: 배열, 연결 리스트, 스택, 큐

💡 선형구조?
한 원소 뒤에 하나의 원소만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조

③ 비선형 구조: 트리, 그래프

💡 비선형 구조?
원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절하다.

📌 시간 복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계
빅오표기법(Big-O notation)
- 점근적 표기법(함수의 증감추세를 비교하는 방법)을 따른다.
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

💡 컴퓨터 과학에서 로그의 밑은 기본적으로 2이다.

// 시간 복잡도 예시
// O(n)
for(let i = 0; i < n; i+=1) {
    //...
}

// O(log n)
for(let i = 1; i <= n; i*=2) {
    //...
}

// O(n log n)
for(let i = 0; i < n; i+=1) {
    for(let j = 1; j <= n; j*=2) {
         //...
    }
}

// O(n²)
for(let i = 0; i < n; i+=1) {
    for(let j = 0; j < n; j+=1) {
        //...
    }
}

빅오표기법의 4가지 법칙
① 계수 법칙
- 상수 k가 0보다 클 때 f(n)=O(g(n))이면 kf(n) = O(g(n))이다.
  n이 무한에 가까울 수록 k의 크기는 의미가 없기 때문이다.

// 계수 법칙: 두 루프는 같은 O(n)이다.
for(let i = 0; i < n; i+=1) {
    //...
}
for(let i = 0; i < n*5; i+=1) {
    //...
}

② 합의 법칙

빅오는 더해질 수 있다.

// 합의 법칙: 두 루프를 합쳐 O(n+m)으로 표기할 수 있다.
for(let i = 0; i < n; i+=1) {
    //...
}
for(let i = 0; i < m*5; i+=1) {
    //...
}

③ 곱의 법칙

빅오는 곱해질 수 있다.

// 곱의 법칙: 두 루프를 곱해 O(n²)으로 표기할 수 있다.
for(let i = 0; i < n; i+=1) {
    for(let j = 0; j < n*5; j+=1) {
        //...
    }
}

④ 다항 법칙

f(n)이 k차 다항식이면 f(n)은 O(n^k)이다.

// 다항 법칙: 다음 루프는 O(n³)으로 표기할 수 있다.
for(let i = 0; i < n*n*n; i+=1) {
    //...
}

🤷‍♂️ 쉽게 말해서...
1. 상수항은 무시
2. 가장 큰 항 외엔 무시

성능 측정 방법
- Date 객체를 이용

시작시간을 구하고 로직을 돌린 다음 끝 시간에서 시작시간을 뺀다

// 성능 측정하기
console.log("start");
const start = new Date().getTime();
const N = 100000000;

let total = 0;
for(let i = 0; i < N; i+=1) {
    total+=i;
}

const end = new Date().getTime();
console.log(end-start);
console.log("finish");

출력 결과: 0.677초 가량 걸림

📌 배열(순차리스트, Array)

연관된 데이터를 연속적인 형태로 구성된 구조를 가진다.
배열에 포함된 원소는 순서대로 번호(index)가 붙는다.
특징
① 고정된 크기를 가지며 일반적으로는 동적으로 크기를 늘릴 수 없다.

💡 자바스크립트처럼 대부분의 스크립트 언어는 동적으로 크기가 증감되도록 만들어져 있다.

② 원하는 원소의 index를 알고 있다면 O(1)로 원소를 찾을 수 있다.

③ 원소를 삭제하면 해당 index에 빈자리가 생긴다.
⌛ 시간 복잡도 계산
① 배열 요소를 삭제하고 앞당기기
- 삭제 후 순서를 맞추려면 O(n)이 소요
② 배열 요소를 중간에 추가
- 중간에 요소를 추가하고 싶다면 O(n)이 소요
- 그렇기 때문에 추가와 삭제가 반복되는 로직에서는 배열 사용을 권장하지 않음
- 탐색이 많은 경우에만 유리

자바스크립트 배열만의 특징
① 동적이다.

② HashMap에 가깝다.

③ index가 number가 아니어도 된다.
배열 생성과 사용법

// 배열 생성

// 1. 빈 배열 생성
let arr1 = [];
console.log(arr1);

// 2. 미리 초기화 된 배열 생성
let arr2 = [1, 2, 3, 4, 5];
console.log(arr2);

// 3. fill 사용 (많은 값을 같은 값으로 초기화할 때)
let arr3 = Array(10).fill(0);
console.log(arr3);

// 4. 특정 로직을 사용한 초기화 (from 이용)
let arr4 = Array.from({ length: 100 }, (_, i) => i);
console.log(arr4);


// 배열 요소 추가, 삭제하기
// 테스트용 배열 생성
const arr = [1, 2, 3];
console.log(arr);

// 끝에 추가
arr.push(4);

// 여러 개를 한 번에 추가
// 맨 뒤 추가는 O(1)의 시간복잡도를 가짐
arr.push(5,6);
console.log(arr);

// 3번 인덱스에 200 추가
arr.splice(3, 0, 200)
console.log(arr);

// 3번 인덱스 값 제거
arr.splice(3, 1);
console.log(arr[3]);