[Javascript] 자료구조란

자료구조는 다수의 data를 담기 위한 구조로 데이터 수가 많아질수록 효율적인 자료구조가 필요하다

성능 비교: 자료구조/알고리즘의 성능 측정 방법에 대해 이해할 필요가 있음

 

1. 선형구조(Linear Data Structure)

:: 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조, 데이터가 일렬로 연속적으로 연결

- 배열

- 연결 리스트

- 스택

- 큐

 

2.비선형구조(Non-Linear Data Structure)

:: 하나의 데이터 뒤에 다른 데이터가 여러 개 올수있는 자료구조, 데이터가 일직선상으로 연결되어있지 않아도 된다.

- 트리

- 그래프

 

성능 측정 방법

• 시간 복잡도(Time complexity): 알고리즘에 사용되는 연산 횟수 측정
• 공간 복잡도(Space complexity) : 알고리즘에 사용되는 메모리의 양을 측정
• 공간을 많이 사용하는 대신 시간을 단축하는 방법이 흔히 사용

 

* 복잡도를 표현할때 Big-O 표기법 사용

1. 특정한 알고리즘이 얼마나 효율적인지 수치적으로 표현

2. 가장 빠르게 증가하는 항만을 고려하는 표기법

 

다음 알고리즘 O(n)의 시간 복잡도를 가진다.

let n = 10;
let summary = 0;

for (let i = 0; i < n; i++) {
	summary += i;
}
console.log(summary) // result 45

 

다음 알고리즘은 O(n²)의 시간 복잡도를 가진다.

let n = 9;

for(let i = 1; i <= n; i++){
	for(let j = 1; j <= n; j++){
 		console.log(`${i} X ${j} = ${i * j}`);   
    }
}

 

일반적으로 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요

ex) n이 1000일때,

O(n): 약 1000번의 연산

O(nlogn): 약 10000번의 연산

O(n²): 약 1,000,000번의 연산

O(n³): 약 1,000,000,000번의 연산

 

Big-O표기법으로 시간 복잡도를 표기할 때는 가장 큰 항만을 표시

가장 큰 항에 붙어있는 계수는 제거

O(3n² + n) = O(n²)

 

코딩 테스트에서 메모리의 크기 일반적으로 MB 단위로 표기

int a[1000] : 4KB

int a[1000000] : 4MB

int a[2000][2000] : 16MB