[Datastructure] Time Complxity with Data Structure

1. Array

• Access : O(1) (바로 접근 가능)
• Search : O(n) (search은 모든 원소를 순회해야 하므로)
• Insertion : O(n) (넣을 index를만들고 이후에 있는 요소들을 한칸씩 뒤로 민다.(n))
• Deletion : O(n) (요소 삭제후 이후에 있는 요소들을 앞으로 당긴다.(n))

---

2. Linked List

• Access : O(n) (해당 노드에 접근하기 위해서는 처음부터 순회를 해야하므로)
• Search : O(n) (해당 노드를 탐색하기 위해서는 처음부터 순회를 해야하므로)
• Insertion : O(1) (삽입이라는 operation만 보면 연산은 상수번(2번) 일어난다.)
• Deletion : O(1) (삭제라는 operation만 보면 연산은 상수번(2번) 일어난다.)

---

3. Hash Table

(hash table은 충돌 가능성이 있기 때문에 average case와 worst case가 다르다.)

• Access : x (순서가 없으므로 접근안됨)

   3.1 average case(충돌 없을때)

• Search : O(1) 해싱값으로 한번에 찾는다.
• Insertion : O(1) 해싱값으로 한번에 삽입한다.
• Deletion : O(1) 해싱값으로 한번에 삭제한다.

   3.2 worst case(충돌가능성때문에 array value를 linked list로 구현하였다면)

• Search : O(n) 해싱값으로 value를 찾으면 그곳이 linked list이므로 2번과 동일하다.
• Insertion : O(n) 해싱값으로 value를 찾으면 그곳이 linked list이므로 2번과 동일하다.
• Deletion : O(n) 해싱값으로 value를 찾으면 그곳이 linked list이므로 2번과 동일하다.

4. Tree

(일반 트리에서의 opertaion은 모든 노드를 순회해야 하므로)

• Access : O(n) 
• Search : O(n)
• Insertion : O(n)
• Deletion : O(n)

5. Binary Search Tree

(bst도 balanced(average case) 와 unbalanced(worst case)가 있다.)

   5.1 balanced(average case) : 자식노드가 2개로 채워져 있는경우

    bst는 값을 찾아나갈때 데이터의수가 n/2 , n/4 , n/8 , ...  이 되고 최종 1개가 남을때 까지 k번 진행되므로

    n * 1/2^k = 1(최종1개) 이고 , 

    n = 2^k이므로, 

    k(횟수)를 구하기 위해서 밑이 2인 log를 씌워주면,

    k = log n ( 밑은 2임 ) 가 된다.

    big o 표기법에서는 밑의 의미가 미미하기때문에 표시는 O(log n )으로 한다.

• Access : O(log n)
• Search : O(log n)
• Insertion : O(log n)
• Deletion : O(log n)

   5.2 unbalanced(worst case) 

    이 경우는 단지 linked list와 다를것이 없다.

• Access : O(n)
• Search : O(n)
• Insertion : O(n)
• Deletion : O(n)