자료 구조

효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장 할 수 있는 데이터 집합을 말합니다

시간 복잡도

시간 복잡도란 문제를 해결해 나가는 데 걸리는 시간과 입력의 함수 관계 를 가리킵니다

빅오표기법

알고리즘의 로직이 얼마나 오랜 시간이 걸리는지 나타내는 표기법

처리(연산)되는 속도가 더 빠르다는건 시간복잡도가 더 적다는 얘기입니다
시간복잡도를 줄일수록 성능이 향상됩니다
처리 시간으로 비교하는거는 측정할때마다 규칙적이지 않을 수 있기 때문에, 연산 개수로 비교하는 것입니다

• 상수시간 O(1)
  • 산술 (+ ,*, /, % )
  • 변수 할당 (=)
  • 인덱스 접근
• 로그시간 O(log n)
• 선형시간 O(n)
  • 루프 연산
• 지수시간 O(n^2)

// O(n) 

// n의 입력값 만큼 loop 선회 하기때문에 선형 형태를 그린다
 function addUpTo(n) {
 	let total = 0;
    for (let i = 1; i <= n; i ++) {
    	total += i;
    }
   return total;
 }

위의 코드와 동일한 결과를 반환하지만 아래의 코드가 더 빠르고, 더 가독성이 좋으며, 더 적은 메모리를 사용한다

// O(1)

// n값과 상관없이 항상 3가자의 연산이 이루어진다 * , + , /
function addUpTo(n) {
	return n * (n + 1) / 2;
}

시간복잡도 Perfomance Tracker
https://rithmschool.github.io/function-timer-demo/

자바스크립트 메서드에 대한 시간 복잡도

Array

• 삽입
  • push - O(1) : 기존 요소들의 인덱스 변화 X
  • unshift - O(n) : 기존 요소들의 인덱스 변화 O
• 삭제
  • pop- O(1) : 기존 요소들의 인덱스 변화 X
  • shift - O(n) : 기존 요소들의 인덱스 변화 O
• 탐색 - O(n)
• 접근 - O(1) : 인덱스로 접근

추가 배열 메서드

• concat - O(n)
• slice - O(n)
• splice - O(n)
• sort - O(nLog n) -> 가장 느림
• forEach / map / filter / reduce - O(n)

Object

• 삽입 - O(1)
• 삭제 - O(1)
• 탐색 - O(n)
• 접근 - O(1)

 let instructor = {
 	firstName : "BORA",
    inInstructor: true,
    favoriteNumbers: [1,2,3,4]
 }
 
// key를 이용한 접근 -> O(1)
 console.log(instructor.firstName); // "BORA"
// key를 이용한 삽입 -> O(1)
instructor.lastName = "KIM"
// key를 이용한 삭제 -> O(1)
delete instructor.lastName;
// 특정 조건에 맞는 value 값을 찾기 위해서는 객체를 순회하며 탐색 -> O(n)
for(const key of instructor) {
	if(instructor[key] === true) {
    	return key;
    }
}
// 객체를 순회하여 key 또는 value 값을 배열로 반환 -> O(n)
Object.keys(instructor); 
Object.values(instructor); 
Object.entries(instructor); 

// 키를 이용한 탐색 -> O(1)
instructor.hasOwnProperty('fisrtName');

공간 복잡도

공간 복잡도란 프로그램을 실행시켰을 때 필요로하는 자원 공간의 양을 말합니다
정적 변수로 선언된 것 이외에도 재귀함수로 인해 동적으로 공간이 필요한 경우도 포함합니다

불변 공간

• boolean
• number
• undefined
• null

O(n) space

• 문자열 길이
• 배열의 길이
• 객채의 키 갯수

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