소오설 소오설

Asymptotic Notation 자료구조를 분석함에 있어서 다양한 작업(Operation)들의 Running time에 대해 논할 때가 있다. 당연히 정확한 Running time은 각각 컴퓨터에 따라 다르게 나타난다. 우리가 어떤 Operation의 Running time에 대해 이야기 할 때는 Operation 도중에 수행되는 컴퓨터의 지시(Computer instructions)의 수를 이르는 것이다. 아주 간단한 코드에서도 이 양[量]은 정확하게 계산해내기 힘들다. 따라서 Running time을 정확하게 계산하는 대신에 우리는 소위 말하는 Big-Oh notation을 사용하기로 한다. 어떤 함수 f(n)에 대해서 O(f(n))은 다음과 같은 함수의 집합을 이르는 것이다. 도표로 생각을 해보..

Summary 다음과 같은 Theorem이 Doubly Linked List의 성질 혹은 Perfomance를 정리한다. Theorem. DLList는 List Interface를 구현할 수 있다. 이 Implementation에서 Add, Remove, Set, Get은 모두 O(1 + min{i, n - i})의 Running time을 갖는다. DLList에서 GetNode의 시간복잡도를 무시한다면 모든 작업이 상수시간 내에 해결된다는 것을 주목할 필요가 있다. 즉, 오직 특정 Node를 찾는 작업만이 시간을 많이 잡아먹고 한 번 Node를 잡으면 어떤 작업도 상수시간 내에 해결할 수 있다. 이것이 Array-Based List와 가장 큰 차이를 나타내는 지점이다. Array-Based List는 ..

Doubly Linked List(以下DLList)는 Singly Linked List와 유사한 형태이다. 차이점이라고 하면 SLList는 Node u가 존재할 때, u->next에 해당하는 정보만을 가지고 있으나 DLList는 Node u에 선행하는 Node w를 가리키는 Pointer혹은 Refernce (u->prev)를 가지고 있다는 점이다. Doubly Linked List SLList를 구현함에 있어서 특별히 주의를 기울여야만 했던 요소들이 있었다. 가령 List끝(tail)의 정보를 제거하는 경우나 크기가 0인(n=0)경우에 Add 작업을 수행하는 경우가 있다. DLList는 이렇게 주의를 기울여야 하는 요소가 더욱 늘어난다. 다양한 상황에 적합하게 대응할 수 있는 방법 중 하나가 Dummy..

The Interface 자료구조를 배우는데 있어서 Interface와 Interface의 Implemetation을 구분하는 것은 매우 중요하다. Interface는 データ構造가 무엇을 하는지 묘사하는 것에 가깝고 자료구조의 Implementations는 실제 データ構造가 행하는 그 무엇을 어떻게 수행하는지 묘사되어 있는 것에 가깝다. An Interface는 종종 Abstract Data Type이라도고 불리는데 이는 자료구조가 제공하는 Operation(혹은 関数나 作業)을 정의하고 해당 Operation의 Semantics나 의미 등을 정의한다. Interface는 자료구조가 어떻게 operations을 implement하는지 알려주지 않는다. 오직 Interface가 가진 Operation의 목..

Array가 아닌 Pointer를 기반으로 list interface를 공부해 보도록 합시다. 여기서 구조는 List Item을 포함하는 노드[Node]로 이루어져 있습니다. 포인터를 이용한 이 노드들은 일련의 연속적인 연결체로서 존재하게 됩니다. 우리는 먼저 FILO Interface ( Stack )와 Queue Operation들을 상수 시간 내에 해결해주는 Singly Linked List ( 以下SLL )를 공부하고 Deque Operation들을 상수 시간 내에 해결해주는 Doubly Linked List에 대해서 공부하기로 합니다. SLL은 Array-Based List Interface와 비교해서 확연한 장단점이 존재합니다. 가장 눈에 띄는 단점은 상수 시간 내에 임의의 자료에 접근하는 S..