맥북왔다 ^^
DataStructure
어제 까지 구현한 DataStructure 시간이 조금 남아서 다시 처음 부터 구현하는 시간을 가졌다. 물론 다 하진 못했지만... Stack, Queue에 대한 내용을 블로깅 하였다.
Graph도 진행 하였지만 다른 자료구조도 함께 정리해야 할 것 같아서 일단 미뤄뒀다.
Time Complexity
오늘은 복잡도에 대한 내용을 배웠다.
시간과 공간은 무한이 아니라서 중요하다고 할 수 있다. 문제의 용량이 커질수록 결과가 빠르게도 비슷하게도 훨씬 느리게도 진행될 수 있다.
예를 들어 배열에서 가장 큰 수와 가장 작은 수의 차를 구할 때,
접근의 방법을 3가지로 나눠 볼수 있다.
- 모든 수들의 차를 구한다.
- 가장 작은 수와 큰수를 구하여 뺀다.
- 정렬된 상태라고 가정했을때, 처음 인덱스와 마지막 인덱스를 가져온다.
1번에서는 총 n^2, 2번에서는 2n, 3번에서는 3번의 연산이 필요하다.
위 배열에서 구현한 것을 Big-O notation을 활용하여 표현하면 각각 O(n^2), O(n), O(1)이 된다.
+)Big-O Notation
-
O(1) -> constant //배열 픽업, 해시 테이블 추가
-
O(log n) -> ogarithmic // 트리 순환
-
O(n) -> linear // 링크드 리스트, array에서 찾는 것
-
O(n^2) -> quadratic //이중 for문
-
O(C^n) -> exponential // recursion
또한 Array와 linked List, Tree로 비교해 보았다.
Array
-
데이터 가져오기, 할당 -> O(1)//인덱스로 바로 접근
-
삽입, 삭제 -> O(n)// 인덱스가 밀리거나 앞으로 당겨져야(?) 하기 때문이다.
-
탐색 -> O(n)
Linked List
Linked List의 삭제는 코드에서 어떠한 reference로도 접근을 할 수 없으면 삭제라고 판단된다.
-
삽입 -> O(1) // 삽입하고 참조만 바꿔준다
-
삭제 -> O(1) or O(n) // 노드는 자신의 전 노드를 모르기 때문에 pointer가 자신을 가르키는 노드를 찾아서 참조를 바꿔줘야 한다. 그러나 head는 그럴 필요가 없기 때문에 head: O(1), middle: O(n)이다
(Double-linked List는 위치가 어디든지 O(1)) -
탐색 -> O(n)
Tree
- 탐색 -> O(n) // 깊이 우선이나 너비우선으로 다 찾아야 한다.
그러나 BST라면 탐색은 O(log n)이다.
그러나 BTS라도 최악의 경우에는 O(n)이다.
방지하는 방법은 왼쪽의 depth와 오른쪽의 depth가 1이 초과 되면 밸런스가 좋지 않다고 하는데, 밸런스가 무너질 때마다 밸런스 확인 후 조정해야 한다.
배열은 연속적인 블럭을 차지하나 BST는 비 연속적 메모리를 가지고 있어 메모리를 더 효율적으로 사용할 수 있다.
데이터 구조는 각 장단점이 있는데 그것을 알아야 쓸 때 더 효율적으로 데이터구조를 찾고 사용할 수 있기 때문에 알아둬야 한다고 한다.
hashtable O(n)은 워스트 인 것이고 ...O(1)이 일반적
