Algorithm PO-Sort(S, C)
Input Sequence S, Comparator C for the elements of S
Output Sequence S sorted in increasing order according to C
P <- priorty queue with comparator C
while ㄱs.empty()
e <- S.front()
S.eraseFront()
P.insert(e, ∅)
while ㄱP.empty()
e <- P.removeMin()
S.insertBack(e)
unsorted list 로 PQ 를 구현
삽입(insert) : O(1)
탐색(min) : O(n)
삭제(removeMin) : O(n)
sorted list 로 PQ 를 구현
삽입(insert) : O(n)
탐색(min) : O(1)
삭제(removeMin) : O(1)
Selection Sort (선택정렬)
O(n^2)
- PQ 배열에 카피후, 최솟값을 PQ 에서 일일이 찾아내서 시퀀스에 옮김
Insertion Sort(삽입정렬)
worst case : O(n^2) // best case : O(n)
- PQ 배열에 원소 하나하나를 넣을때마다 정렬상태를 유지.
정렬 완료후에 시퀀스에 PQ 내용을 카피
O(n^2) = n(n+1)/2
- 시퀀스의 범위를 1칸씩 늘려가면서 유입되는 원소를 정렬시켜줌
- 즉, PQ 에서 최솟값을 찾아서 시퀀스에 삽입 (시퀀스의 범위를 1칸씩 늘려감)
O(n^2) = n(n+1)/2 // best : O(n), average : n^2/4
- PQ의 범위를 1칸씩 늘려가면서 유입되는 새로운 원소를 정렬시켜줌
1단계 : insert연산을 Heap Merge 방식으로 n번 진행 = O(n)
2단계 : O(nlog n)
최악의 경우 비교연산 횟수 = 2 x (빨간 간선 수) ≤ 2 x (총 간선수) ≤ 2 x (총 노드의 수 n)
=> 비교연산 횟수 ≤ 2n = O(n)
왼쪽자식 key < 부모 key < 오른쪽 자식 key
사용공간 : O(n)
탐색(TreeSearch), 삽입(put), 삭제(erase) 연산 모두 O(h)
Algorithm TreeSearch(k, v)
if(v.isExternal())
return v
if k < v.key()
return TreeSearch(k, v.left())
else if k == v.key()
return v
else if k > v.key()
return TreeSearch(k, v.right())
1.일반 BST 연산처럼 TreeSearch() 호출해서 삽입될 external 노드 위치 찾아냄 : O(log n)
2. 삽입 후 AVL의 특성(높이 차가 최대 1) 을 위반하는지 체크: O(log n)
3. 재구성(restructuring) 진행 : O(1)
- 3-1. z, y, x를 설정하고 3개의 트리 재구성 : O(1)
=> single rotation, double rotataion 모두 O(1)- 3-2. 서브트리 T1 or T1 + T2 를 옮기기 : O(1)
- 삭제할 노드 탐색 : O(log n)
- 찾아낸 노드 삭제 : O(1) / O(log n)
(successor 를 찾고 삭제하는 과정이 포함된 case만 O(log n)- 삭제 후 AVL의 특성(높이 차가 최대 1) 을 위반하는지 체크 : O(log n)
- 문제가 발생한 경우, 재구성(restructuring) 진행 : O(log n)
(4번의 경우 재구성 과정 자체는 O(1) 이지만, 재구성 알고리즘을 최악의 경우 O(log n) 번 호출할 수 있다.)
1.로그파일 : unsorted 링크드리스트 기반
2.Search Table (Look up table) : sorted array 기반, 이진탐색 활용
=> 삽입, 삭제가 왜 O(n) 인가?
- 해시테이블 시간복잡도
모든 해싱 기법은 탐색, 삽입, 삭제 연산 실행시간이 동일하다.
expected time : O(1)
worst case : O(n)- 사용공간 : O(n)
case1) 빈 인덱스를 만난경우 => 후보 명단에 없는것
case2) 원하는 key 값을 만난경우
case3) 충돌이 발생하는 경우 => 다음 셀을 확인하러간다. 탐사를 또 진행
Algorithm find(k)
i < - h(k) // 인덱스
p <- 0 // probing 총 횟수
repeat
c <- A[i]
if c = Ø // 1. 원하는 key값을 못 찾은채로 빈 인덱스를 만난경우
return null // => 후보 명단에 없는거임
else if c.key() = k // 2. 원하는 key값 찾은경우
return c.value()
else // 3. 충돌이 발생하는 경우
i <- (i+1) mod N // => 다음 셀을 확인하러 나간다. 탐사를 또 진행
p <- p + 1
until p = N
return null // 배열의 모든 인덱스에 대해 싹다 뒤져봤지만 못찾은 경우
erase 연산
AVAILABLE 은 삽입 연산시에는 비어있다고 인식되서 그냥 데이터를 삽입하면 된다.
반면 탐색, 삭제 연산시에는 빈 상태가 무시되고( = 빈 상태가 아니라고 인식되고) 다음 인덱스로 넘어감
1차 해시함수 : h(k) = k mod N
2차 해시함수 : d(k) = q - k mod q (q: N보다 작은 소수중 가장 큰 소수)
"2차 해시함수의 결과값 d(k)" 만큼 이동해서 탐색을 계속 진행
j번쨰로 탐색하게 되는 인덱스 : (i +j x d(k) ) mod N = h( h(k) + j x d(k) )
즉, 인덱스 i (= 1차해시함수의 결과값 i을 탐색의 시작 인덱스로 설정 ) 가 비었다면 2차 해시함수의 결과값(=d(k)) 만큼 계속 이동하면서 탐색을 진행하는 것이다.
1차해시함수를 바깥에 또 적용시킨 이유는, 환형배열로 구현하기 위함
vertex 오브젝트 구성요소
1) 데이터
2) vertex 시퀀스에 다시 돌아가기 위한 주소값
edge 오브젝트
1) 데이터
2) source vertex 오브젝트 주소값
3) destination vertex 오브젝트 주소값
4) edge 시퀀스에 다시 돌아가기 위한 주소값
edge 에서 vertex 는 따라갈수 있는데, vertex 에서 edge 따라갈 수 없다!
v.incident() : O(m)
v.isAdjacentTo(v) : O(m)
양끝점이 u, v 인 edge 오브젝트가 나올때까지 edge 시퀀스에서 찾아야함
incidence 시퀀스
vertex 오브젝트의 구성요소
1) 데이터
2) vertex 시퀀스에 다시 돌아가기 위한 주소값
3) incidence 시퀀스의 시작 주소
edge 오브젝트 구성요소
1) 데이터
2) source vertex 오브젝트 주소값
3) destination vertex 오브젝트 주소값
4) source vertex 오브젝트의 incidence 시퀀스에서 해당 원소에 대한 주소값
5) destination vertex 오브젝트의 incidence 시퀀스에서 해당 원소에 대한 주소값
6) edge 시퀀스로 다시 돌아가기 위한 주소값
=> 엣지를 삭제하면 양끝 정점의 차수가 1씩 감소한다.
case1) 정점 u,v 의 차수를 알고있는 경우
case2) 정점 u, v 의 차수(degree) 를 모르는 경우
정점 u,v 를 계속 번갈아가면서 반대편(opposite) 정점을 가리키는 edge 오브젝트가 있는지 확인
=> 따라서 행 or 열의 크기인 O(n) 만큼의 시간이 걸린다.
Algorithm DFS(G)
Input graph G
Output labeling of the edges of G as discovery edges and back edges
for all u ∈ G.vertices()
u.setLabel(UNEXPLORED)
for all
for all e ∈ G.vertices()
e.setLabel(UNEXPLORED)
for all v ∈ G.vertices()
if v.getLabe() = UNEXPLORED
DFS(G, v)
Algorithm DFS(G, v)
Input graph G and start vertex of G
Ouput labeling of the edges of G in the connected component of v as discovery edges and back edges
v.setLabel(VISITED)
for all e ∈ G.incidentEdges(v)
if e.getLabel() = UNEXPLORED
w <- e.opposite(v)
if w.getLabel() = UNEXPOLRED
e.setLabel(DISCOVERY)
DFS(G, w)
else
e.setLabel(BACK)
Algorithm BFS(G, v)
L0 <- new empty sequence // queue
L0.insertBack(v)
i <- 0
while ㄱ Li.empty()
Li+1 <- new empty sequence
for all v ∈ Li.elements()
for all e ∈ v.incidentEdges()
if e.getLabel() = UNEXPLORED
w <- e.opposite(v)
if w.getLabel() = UNEXPLORED
e.setLabel(DISCOVERY)
w.setLabel(VISITED)
Li+1.insertBack(w)
else
e.setLabel(CROSS)
i <- i+1
Algorihtm topologicalDFS(G)
Input dag G
Output topological ordering of G
n <- G.numVertices()
for all u ∈ G.vertices()
u.setLabel(UNEXPLORED)
for all v ∈ G.vertices()
if v.getLabel() = UNEXPLORED
topologicalDFS(G, v)
Algorithm topological(G, v)
Input graph G and start vertex of V
Output labeling of the vertices of G in the connected component of v
v.setLabel(VISITED)
for all e ∈ v.outEdges()
w <- e.opposite(v)
if w.getLabel() = UNEXPLORED
{ e is a discovery edge }
topologicalDFS(G, w)
else
{ e is a forward or cross edge }
Label v with topological number of n
n <- n-1
Algorthm Topological(G)
H <- G
n <- G.numVertices()
while H is not empty do
Let v be vertex width no outgoing edges
Label v <- n
n <- n-1
Remove v from H
Algorithm Topological(G)
S <- an initally empty stack
for all u in G.vertices() do // incoming 간선이 없는 정점들을 모두 스택에 push
Let incounter(u) be the in-degree of u
if incounter(u) = 0 then S.push(u)
i <- 0
while !S.empty() do
u <- S.pop()
Let u be vertex number i in the topological ordering
i <- i + 1
for all outgoing edges (u, w) of u do
incounter(w) <- incounter(w) - 1
if incounter(w) = 0 then S.push(w)