Algorithm 10 - Amortized Analysis & Graph Algorithm

 Amortized Analysis
연속된 operation의 time complexity & space complexity를 계산하는 방법. 이는 대부분의 operation은 긴 시간이 걸리지 않지만, 특정 operation만 시간이 걸리는 경우에 효율적으로 사용될 수 있다. 왜냐하면 앞서 heap sort에서 본 것 처럼, worst case method를 사용하면 너무 큰 결과가 나올 수 있기 때문이다. (not-tight enough)

따라서 여러 개의 operation이 있을 때 최악의 경우를 평균을 내어 계산할 수 있다. 예를 들어 전체 operation의 n개의 worst case cost가 T(n)이라 할 때, amortized cost per operation은 total cost를 평균 내어 계산할 수 있다. (amortized cost = T(n)/n - aggregating method)

Accounting Method
전체에 대해 같은 amortized cost를 배정하므로 operation에 따라 실제 cost보다 클 수도 있고, 작을 수도 있다. 이를 credit(prepaid cost) 라 한다.
따라서 전체 operation 들의 amortized cost의 합은 각 operation의 실제 cost의 합보다 커야 한다. 만약 그렇지 않다면 upper bound를 제공하는 의미가 없어지기 때문이다.

연속적인 연산에 대해서 선행되는 연산이 추후 실행될 연산을 결정한다면, 이를 미리 계산하는 것이 credit의 의미가 된다. 예를 들어 stack 연산이 있다면, stack에 push를 해야 pop을 할 수 있으므로 push와 pop 모두 실제 cost는 1이지만, amortized cost는 push가 2, pop은 0의 cost를 가지게 할당하는 것이다. 이 때 전체 credit의 합은 후행되는 연산의 cost보다 크거나 같아야 한다. (더 적은 cost가 되면 안됨)

Potential Method
Accounting method와 비슷하지만, credit을 potential energy로 변환한 것. 어떤 연산의 amortized cost는 실제 cost에 해당 연산으로 인해 변화한 potential energy 만큼을 더해준 값으로 구할 수 있다. 만약 potential energy 항이 0보다 크다면, credit을 부여한 것과 같으며(추후 연산에 대한 코스트를 미리 계산) potential energy항이 0보다 작다면, 저장된 에너지를 이용할 수 있으므로 선행된 연산이 cost를 지불하였으므로 실제 cost보다 적은 cost를 가지게 된다.

credit과 다른 점은 이 potential energy를 결정하는 function을 구해야 하는 것이다. 그리고 앞서와 동일하게, 전체 cost보다 potential energy의 합이 크거나 같다는 조건을 만족해야 한다. (실제 상황에서는 몇 개의 연산이 있을 지 확정할 수 없으므로 초기 에너지를 0으로 가정한다. 이는 물리학 문제를 풀 때 가장 낮은 물체의 위치 에너지를 0으로 설정하고 계산하는 것과 동일하다)

종합하면, 이는 몇 개의 cost가 높은 operation의 부담을 다른 operation 들에게 spread 하여 더 tight한 upper bound를 계산하는 방법이다.


Dynamic tables
상기한 여러 문제의 실용적인 사용 시나리오. 어떤 table에 실제로 몇 개의 데이터가 들어갈 지 알 수 없으므로 table을 expansion / contraction  해야 한다.따라서 amortized cost of insertion & deletion 이 O(1)임을 보이고, space을 가장 효율적으로 사용하는 방법을 찾아야 한다. (unused space가 전체의 상수비율)


Graph Algorithm
Graph : entity - relation으로 구성된 객체 사이의 관계를 나타내는데 사용하는 Data Structure.
- G(V, E) : Vertex(=node), Edge. edge에 방향성이 있다면 이를 directed graph라 하고, 방향성이 없다면 undirected가 된다.
- Degree : 하나의 노드에 연결된 relation의 수로, 만약 방향성이 존재한다면 income/ outgoing으로 구분하여 표기한다. 방향성이 없을 경우 그냥 해당 노드와 연결된 edge의 수가 degree가 된다.

- path : 방문하는 sequence of vertice를 나열한 것으로 연속된 두 노드 간에는 이동가능한 edge가 있어야 한다. 만약 해당 path를 구성하는 모든 node가 distinct하다면 이를 simple path라 한다.

-cycle : 시작점과 종료지점이 같은 path를 cycle이라 하며 path 와 동일하게 겹치는 노드가 없을 경우 이를 simple cycle이라 한다.
또한 어떤 그래프에서 cycle 가능한 path가 없을 경우 이를 Acyclic graph라 한다.

이런 그래프는 adjacency-matrix(인접행렬)와 adjacency-list(인접 리스트)의 두 가지 방법으로 표현할 수 있다.

인접행렬
인접 행렬로 나타내는 경우, 노드 i와 j 사이에 edge가 있을 경우, A[i][j]를 1로 표기하면 된다. 반대로 edge가 없다면 0이 된다. directed graph는 edge의 방향성을 따져야 하므로 i와 j 가 바뀌면 다른 값을 가질 수 있지만, undirected graph는 방향성이 없으므로 diagonal을 기준으로 대칭을 띄게 된다.

이 방법의 space complexity는 vertice의 개수 V의 제곱만큼 필요하므로 O(v2)이 된다. 또한 edge가 존재하지 않는 0의 값도 모두 저장해야 하므로 공간의 낭비가 발생한다.
그러나 time complexity의 경우, A[i][j] 의 edge가 존재하는지 확인할 때는 O(1) (배열이므로 direct access 가능) , neighbor를 확인할 때는 O(v) (해당 i / j를 모두 확인), 전체를 확인할 때는 O(v2)가 걸린다.

인접 리스트
인접 리스트는 각 노드를 헤드로 가지는 연결리스트를 생성하여 해당 노드와 인접한 노들을 연결하는 방식으로 그래프를 표현한다.
이 경우, space complexity는 O(V+E)만 필요하다. 왜냐하면 이전과 달리 edge가 존재할 때만 저장하면 되기 때문이다.
따라서 각 edge / neighbor 를 확인하는데 걸리는 time complexity는 O(degree of the node), O(E)가 된다. 전체를 확인하는데 걸리는 시간은 O(E)이다.

정리하면, 그래프의 노드 수와 이들 사이 존재하는 간선 수에 따라 더 효율적인 것을 적절히 사용하면 된다.
예를 들어 만약 노드 수가 훨씬 적을 경우, 인접 행렬은 대부분이 0으로 채워져 공간 낭비가 심해진다. 그러나 만약 노드 개수의 제곱보다 간선 수가 많거나 비슷할 경우, 인접 리스트보다 인접 행렬이 더 효율적으로 저장, 검색할 수 있다.

Tree & Graph
tree가 graph보다 더 좁은 범주를 가리킨다. 따라서 모든 트리는 그래프지만, 그래프라고 반드시 트리인 것은 아니다. 그래프가 트리가 되려면 모든 노드가 서로 연결되어 있고, cycle이 없다는 조건을 만족해야 한다.

Searching Algorithm
그래프에서 특정 노드를 찾거나, 해당 노드로 이동 가능한 노드를 확인하거나, 두 노드 사이 가장 짧은 경로를 찾는 경우 그래프의 searching algorithm이 필요하다.

- Breath-First search (BFS) : 큐를 사용하여 구현
이 방법은 현재 노드로부터 가장 가까운 것들부터 순서대로 확인하는 것이다. (explore every reachable vertex first) 따라서 어떤 노드와 연결된 노드들을 모두 큐에 넣은 후 하나씩 꺼내가며 방문하고, 방문한 노드로 부터 가능한 노드를 또 큐에 넣어가며 진행하는 방식이다.

이를 통해 시작 노드에서 몇 단계를 거쳐 해당 노드로 갈 수 있는지 tree를 구성할 수 있다. (breadth first tree) 이를 통해 source vertex에 대한 insight를 얻을 수 있다.

이 방법의 time complexity는 O(V+E)이다. 각 노드는 반드시 한 번 이상 방문되며, 각 간선은 두 번이상 방문된다.

- Depth-First search (DFS) : 스택을 사용하여 구현
이 방법은 현재 노드가 갈 수 있는 경로의 끝까지 갔다가, 분기점으로 다시 돌아와 다른 선택지의 끝까지 가는 경로를 반복하는 것이다. 여기서는 딱히 source node라는 것을 따지지 않는다. 이는 인접한 노드를 recursively deeper한 방법으로 방문한다.
만약 연결되지 않아 방문할 수 없는 노드가 있으면 새로운 search를 시작한다.

DFS의 time complexity는 O(V+E)가 된다. 코드 논리 상으로는 V*E가 되어야 할 것 같지만 앞서 살펴본 것 처럼(aggregate analysis) 이는 tight하지 않다는 것을 알 수 있다. (왜냐하면 stack에서 pop할 수 있는 것은 push 한 개수만큼 가능하므로)

DFS는 depth-first forest를 구성하며 이는 여러 개의 그래프들 간의 connectivity information을 담고 있다. 이는 이전과 달리 노드 간의 관계는 담고 있지 않다. 그래서 각 그래프 사이의 관계나 cycle의 유무, short cut 등을 찾아볼 수 있다.