[TIL] 0105

 

알고리즘

 

시간 복잡도 / 공간 복잡도 / 배열 /  링크드리스트

 

1) 시간 복잡도 - 반복문과 밀접하며 프로그램 수행 성능을 '최악의 경우를 가정’하여 정량화하는 방법.

문제를 해결하는데 걸리는 시간과 입력의 함수 관계

 

2) 공간 복잡도 

n개의 입력이 주어지면 공간을 얼만큼 쓰는지 나타내는 것

 

3) 배열

동적배열 : 사이즈가 정해져있지 않음

정적배열 : 사이즈를 정의하고 사용

 

배열을 생성하면 메모리에 연속적인 위치에 존재하여 하나의 변수에 여러 정보를 담을 수 있다.

 

배열에서 할 수 있는 기능

* 조회 - const val = a[2];  / 한 번에 자료를 꺼내올 수 있음 / O(1) 의 조회시간을 가진다.

* 삽입 & 삭제 - 배열의 끝에서는 O(1), 다른 곳은 O(n)

* 정렬

* 검색 - 일반적으로 O(N)이나, 정렬된 배열이면 O(logN)이 가능하다.

 

4) 링크드리스트

유동적으로 연결고리를 떼었다가 붙였다가 할 수 있는 자료구조

 

링크드리스트 용어

노드 - 각 화물 칸들, 맨 앞의 노드를 head, 맨 뒤의 노드를 tail, 맨 뒤의 노드는 포인터가 NULL

현재 노드가 가리키는 다음 화물 칸을 포인터 라고 한다.

 

원소의 삽입/삭제에 강점, 조회에는 약점

 

 

 

/// 

자바스크립트의 데이터 타입

 

1) 데이터 타입의 종류

 

기본형과 참조형은 값의 저장 방식 (주소값을 바로 복제 / 주소값들로 이루어진 묶음을 가리키는 주소값을 복제,

                               불변성 여부 (o/x)를 기준으로 구분된다.

 

2) 메모리와 데이터

비트 : 컴퓨터가 이해할 수 있는 가장 작은 단위 

8개의 비트 = 1 바이트

 

var test = 3 // var 변수, 식별자 = 데이터, 변수명

 

3) 변수 선언과 데이터 할당  // var str = "test";

 - 값을 바로 변수에 대입하지 않는 이유는 자유로운 데이터 변환, 메모리의 효율적인 관리 때문이다.

                                                            ㄴ데이터가 밀리지 않아요          ㄴ변수가 많아질수록 효율적

 

4) 기본형 & 참조형 데이터

 

ex) 

var obj1 = {

 a:1,

 b:'bbb',

};

 

변수영역	주소	1001	1002	1003
	데이터	obj1/ @7103~
데이터영역	주소	5001	5002	5003
	데이터	1	'bbb'
obj1 별도 영역	주소	7103	7104	7105
	데이터	a /@5001	b /@5002

 

참조형 데이터는 기본형 데이터와 다르게 객체의 변수(프로퍼티) 영역이 별도로 존재한다.

데이터에 저장된 값 변경은 불가하나, 별도로 존재하는 변수 영역이 변경 가능하기 때문에 가변 이라고 한다.

arr 의 경우에도 별도의 영역이 필요하다.

 

* 참조카운트 : 객체를 참조하는 변수나 다른 객체의 수를 나타내는 값, 0인 객체는 가비지 컬렉터 에 의해 메모리에서 제거된다.

 

var obj2 = obj1; 

obj1 === obj2;

변수를 복사하여 값을 변경하는 경우에는 객체의 프로퍼티(=속성)에 접근해서 변경하지 않고,

객체 자체를 변경하는 방식으로 변경해야 한다.

 

5) 불변 객체

얕은 복사 : 바로 아래 단계의 값만 복사

깊은 복사 : 내부의 모든 값들을 하나하나 다 찾아서 복사 / 객체 프로퍼티 중 기본형 데이터는 그대로 복사 + 참조형 데이터는 다시 그 내부의 프로퍼티를 복사 하는 것을 재귀적으로 수행하여 완벽한 구현이 가능

 

6) undefined / null : 없음을 나타내는 값

undefined : JS 엔진이 값이 있어야 할 것 같은데 없는 경우 자동으로 부여한다.

null : 없다 라는 것을 명시적으로 표현할 때 사용한다.