5. Data Structure - Time Complexity

1. Arrays

(JS가 아닌 다른 언어)Memory 상에서 이어져 있는 자료구조이다. (primitive data structure)

Time Complexity

1) Lookup(position) time complexity: O(1)

메모리상 이어 붙여져 있기 때문에 index로 바로 찾아갈 수 있기 때문이다.

2) Assign time complexity: O(1)

이것 역시 index 사용해서 다른 값 넣어주면 되니까.

3) Insert time complexity: O(n)

4) Remove time complexity: O(n)

앞의 Insert와 마찬가지로 삭제 후 그 뒤의 것들을 한 칸씩 옮겨 줘야 하니까

5) Find time complexity: O(n)

하나씩 확인하다가, 최악의 경우 찾는 경우는 전부 다 확인해 봐야하기때문에

 

2. Linked List

: Array는 메모리상에서 연속적이지만, Linked list는 그렇지 않아서 reference로 다음이 무엇인지 알려주는 구조로 되어있다. 그래서 head를 알고 있어야 처음시작을 할 수 있다.(double linked list는 tail도 알아야 함)

 

Garbage Collector:

reference가 다 끊어져서 접근이 불가능하면 garbage collector가 이를 가져가서 회수한다.

Time Complexity

1) Lookup(position) time complexity: O(n)

메모리가 렌덤하기 때문에 head부터 reference를 타고 하나씩 확인해야 한다.

2) Assign time complexity: O(n)

Lookup과 동일한 이유이다. 

3) Insert time complexity:

• 마지막에 add하는 경우 : O(1)
• 중간에 insert하는 경우: O(1)
  
  즉, 내가 어디 insert해야 할 지 알고 있다면 O(1)
  모르면 그 값이 들어있는 node를 찾아야 하는 과정이 필요하기 때문에 O(n)

4) Remove time complexity: O(n)

• tail을 remove: O(1)
• midddle의 것을 remove: 내 전의 애를 알아야 garvage collector를 쓸 수 있으니까 내 전의 애를 찾는데 걸리는 시간이 O(n)

5) Find time complexity: O(n)

Lookup과 동일한 이유이다. 

 

3. Doubled Linked List

Time Complexity

나머지는 Single Linked List와 동일한데

Remove time Complexity의 middle remove: O(1)

만 내 앞의 것을 찾을 필요가 없이 바로 알 고 있으니까 O(n) 이 아니라 **O(1)**이다.

 

4. Tree

Time Complexity

Find time complexity: O(n)

DFS나 BFS를 하여야 하는데, 어쨌든 최악의 경우 다 확인을 해야 한다. O(n)

최악의 경우를 생각하면, 맨 처음에 넣으려면 배열의 원소들 다 자리 옮기도 나서 추가 가능하기 때문

 

5. Binary Search Tree

Time Complexity

Find time complexity: children이 특정 조건을 가지고 있기 때문에 최고의 경우(O(log n)), 최악의 경우(왼쪽의 depth와 오른쪽의 depth의 차이가 1 이상일 경우) **(O(n))**가 다르다.

 

6. Stack

Linked Stack

Pros – The stack size is not limited.

Cons – The implementation is complex. – It takes a long time to insert or delete.

Stack Implementation using Arrays

Pros – The implementation is simple. – Insertion or deletion operations are fast.

Cons – The stack size is limited.

Time Complexity

1) push : O(1)

시간 복잡도는 무조건 1입니다. 무조건 제일 위에 들어가니까 시간복잡도가 필요가 없어요.

2) pop : O(1)

무조건 제일 위에걸 빼니까 시간복잡도가 상수시간이 나옵니다.

3) peek : O(1)

이하 동문

4) empty : O(1)

이게 null인지 아닌지만 확인해주면 됩니다. 무조건 시간복잡도가 1이 나옵니다.

5) size : O(1) or O(n)

이게 스택의 구현방식에 따라 다릅니다. 만약 스택을 배열로 만들면 무조건 시간 복잡도가 1이나옵니다.

왜냐하면 배열을 만들때는 항상 level을 기재하고 있기 때문입니다. 그래야 다음 순서 배열로 접근할 수 있으니까.

그러나 리스트로 구현할 경우 내부적으로 끝에서 끝까지 운행을 끝마쳐야 level을 알 수 있습니다.

즉 이 때 시간복잡도는 O(n)이 됩니다.

[출처] 04-자료구조: 스택(Stack)|작성자 저스트쿠카로

 

7. Queue

Time Complexity

1) size(): 현재 큐에 들어 있는 데이터 원소의 수 O(1)

2) isEmpty(): 현재 큐가 비어 있는지 판단 O(1)

3) enqueue(x): 데이터 원소 큐에 추가 O(1)

4) dequeue: 큐에 맨 앞에 저장된 데이터 원소 제기 or 반환 O(n)

왜냐하면 반환하고 나머지것들은 앞으로 한 칸씩 땡겨와줘야 하기 때문
peek() - 큐의 맨앞에 저장된 데이터 원소 반환(제거 x) O(1)