공대생 정리노트

그래프 G=(V,E)에서 신장 트리는 정점 집합 V를 그대로 두고 간선을 |V| - 1개만 남겨 트리가 되도록 만든 것이다. 간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소 신장 트리라고 한다. 프림 알고리즘 집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워나간다. 맨 처음 정점을 제외하고는 정점을 하나 더할 때마다 간선이 하나씩 확정된다. 배열 d[]를 각 정점을 신장 트리에 포함시키는 비용을 구하는데 사용한다. tree[v]는 정점 v를 신장 트리에 연결시키는 비용이 가장 적게 드는 간선을 저장한다. 1. 시작 정점 r의 연결 비용을 0으로, 나머지 정점들의 연결 비용을 무한대로 초기화한다. 2. 정점 r을 집합 S의 첫번째 원소로 포함시킨다. 그 후 r에 연..

분할의 균형이 맞지 않게 분할이 된 상태에서 찾고자 하는 원소가 큰 그룹에 들어가는 일이 반복되면 성능이 선형을 넘어서게 된다. 반면 일정한 상수비를 지켜서 계속 분할이 된다면 복잡도는 항상 O(n)이 된다. 즉, 99:1로 분할이 계속 되어도 최악의 경우에도 O(n)을 만족한다는 것이다. T(n) = T(99n/100) + O(n) 최악의 경우 선형 시간 선택 알고리즘 알고리즘의 대략적인 방법은 다음과 같다. 0. 전체 원소가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다. 1. 전체 원소를 5개씩의 원소를 가진 그룹들로 나눈다.(이때 꼭 5개일 필요는 없다) 2. 각 그룹에서 중앙값을 찾는다. -> 상수시간 * O(n/5) = O(n) 3. 중앙값들의 중앙값을 구한다. 이때 구하는 방법은 이 알..

n개의 원소가 규칙없이 저장된 배열에서 i번째 작은 원소를 찾으려 한다. 분할 알고리즘 사용 quick sort에서 사용하는 것 처럼 기준 원소 하나를 고르고 기준 원소보다 작거나 같은 원소는 왼쪽 그룹으로, 큰 원소들은 오른쪽 그룹으로 재배치한다. 이렇게 하면 기준 원소가 전체에서 몇 번째 원소인지를 알 수 있다. 만약 기준 원소가 k번째로 작은 원소라고 해보자. i가 k보다 작다면 왼쪽 그룹에 있을 것이고, 크다면 오른쪽 그룹에 있을 것이다. 이를 재귀적으로 호출한다면 어떻게 될까? n개의 원소에서 사용되는 비용을 T(n)이라고 하자. 기준 원소가 전체 집합에서 k번째로 작은 원소라면 두 그룹은 k-1개와 n-k로 나뉜다. 그렇다면 식을 다음과 같이 쓸 수 있다. T(n) ≤ max[T(k-1), T..