Time Complexity Analysis와 Data Structure - Data Structure

그 문제를 풀 때 시간과 공간을 얼마나 차지하는지

시간과 공간의 복잡도? 알고리즘이 얼마나 효율적인가를 알 수 있음

사실 프로그래밍 인터뷰에서 자주 묻기 때문에 중요해!

알고리즘을 짤 때, 

1.돌아가는가

2. 시간복잡도

3. 공간복잡도

순으로 중요

 

Constant Time = 요소의 갯수와 상관 없이 정해진 횟수만 실행되면 답이 나오는 것

 

Big-O Notation을 구하는 방식

3 -> O(1)

2n -> O(n)

2n + 3 -> O(n)

n^2 -> O(n^2)

--> 최악의 연산 경우의 수에서 최고차 항만 남고 계수를 제거한 것을 Big-O Notation이라고 보면 된다.

(지수가 높은 것이 커지는 것을 지수가 낮은 것이 따라잡기 어렵기 때문에 이렇게 표현하는 것)

 

Big-O Notation으로 보는 시간 복잡도 

빠름<-O(1)--O(log n)--O(n)--O(n*log n)--O(n^2)--O(c^n)->느림

 

-O(1) -> constant(상수)

문제의 크기가 커져도 시간을 일정

ex)배열에서 특정 인덱스 찾아보기, 해시테이블 추가

 

-O(log n) -> logarithmic(로그)

처음에는 빠르게 증가하다 뒤로 갈 수록 증가 폭이 줄어듦

ex)binary search tree에서 검색

 

-O(n) ->linear(리니어)

ex)linked list 검색, array 검색

 

-O(n^2) -> quadratic(제곱)

문제의 수가 증가할수록 시간이 기하급수적으로 증가

ex)이중for문

 

-O(c^n) -> exponential(지수)

시작하자마자 급격하게 가깝게 증가

ex) 재귀, 피보나치 수열

 

-------------------

Array Data Structure의 특징

- 메모리 상에서 사이즈를 정해주면 사이즈를 할당할 곳들을 찾아 이어줌(자바스크립트 제외). primitive data structure라고 불림 array로 다른 데이터 구조를 만들 수 있어서

Arrays : Lookup : 위치 찾기

시간 복잡도 : O(1)

Arrays : Assign : 할당하기

시간복잡도 : O(1)

Arrays : Insert : 삽입하기

시간복잡도 : O(n) (인덱스 값을 옮겨야 하므로)

Arrays : Remove : 지우기

시간 복잡도 : O(n) (인덱스 값을 옮겨야 하므로)

Arrays : Finde(value) : 값 찾기 

시간 복잡도 : O(n)(최악의 경우 데이터의 갯수만큼 조회해야 하므로)

 

 

Linked List Data Structure의 특징

-Array는 처음 만들게 되면 메모리 상에서 쭉 붙지만 Linked List는 그렇지 않고 랜덤으로 존재하며 각각이 다음이 어디에 있는지 위치가 존재. 어떤 레퍼런스로도 메모리에 접근이 불가능하면 삭제가 된 것으로 인식돼서 가비지 컬렉터가 메모리 공간을 비운다.

Singly-Linked List : Lookup : 위치 찾기,

Singly-Linked List : Find : 값 찾기,

Singly-Linked List : Assign : 할당하기

셋 다 시간 복잡도가 : O(n) (head부터 쭉 찾아야 하므로)

Singly-Linked List : Insert : 추가

시간 복잡도 : O(1) (내가 어디에 추가할건지 알고 있다면)

Singly-Linked List : Remove : 제거

시간 복잡도 : 헤드라면 : O(1), 중간이라면 : O(n)

 

Doubly-Linked List : Lookup : 위치 찾기,

Doubly-Linked List : Find : 값 찾기,

Doubly-Linked List : Assign : 할당하기

셋 다 시간 복잡도가 : O(n) (head부터 쭉 찾아야 하므로)

Doubly-Linked List : Insert : 추가

시간 복잡도 : O(1)

Doubly-Linked List : Remove : 제거

시간 복잡도 :  O(1) (Doubly-Linked List에서는 하나가 앞뒤의 위치를 가지고 있기에 O(1)이다)

 

Tree List Data Structure의 특징

-Tree는 자신의 값과 parents와 children이라는 레퍼런스를 가진다.

Tree : Find 

시간 복잡도 : O(n)

Binary Search Tree : Find : O(log n) (왼쪽은 부모가 작고 오른쪽은 부모보다 크다는 규칙 때문에)

시간 복잡도 : O(1)

 

*메모리단에서 이진 검색 트리(Binary Search Tree: BST와 정렬된 배열(Sorted Array)의 비교

배열은 메모리에 continguos memory를 차지하지만 이진 검색 트리는 Linked List로서 메모리를 구석구석 사용하면서 구조화 하기 때문에 정렬된 배열보다 메모리 사용 관점에서는 이진 검색 트리가 더 낫다.