컴퓨터 알고리즘 중간정리
Amortized analysis(할부상환 시간복잡도)
: 더 많은 연산이 일어나는 연산자에게 더 비싼 값을 치르게 함으로써, 평균에 가까운 시간복잡도를 내놓는다.
: multipop 함수를 씀으로, push를 하는데 2$가, 스택이 안비어 있다면 pop을 하는데 $0가 든다고 가정해보자. 그런 다음 알고리즘의 실행 시간을 달러로 측정해보자.
| 다음 작업과 연결된 목록이 있습니다 • Add Last(x): x 요소를 목록의 끝에 추가합니다 -> 1$ • Remove Thirds(): 목록의 모든 세 번째 요소를 제거합니다. 즉, 목록의 첫 번째, 네 번째, 일곱 번째 등의 요소를 제거합니다. -> 3$ • 예상 비용은 다음과 같습니다 -> 3$ • Add Last(x) - 비용은 1입니다 -> 4$, 실제사용시 1$만 사용하고 3$는 저장 • Remove Thirds() - 비용은 목록의 요소 수와 같습니다 ->0$ 문제 1: 우리가 목록에서 n개의 작업을 수행한다고 가정합니다. Remove Thirds에 대한 통화 중 최악의 경우 실행 시간은 언제입니까? 최악의 경우에는 Add Last 작업을 n-1번 호출한 다음 Remove Thirds를 호출합니다. 따라서 O(n) |
받은건 2$인데 push에서 1$를 쓰고 1$는 저장해두었다가, pop할때 1$를 씀. 근데 2$받은건 push에 받았다고 치자~ 하는 것이다. 이렇게 해야 k의 변동성을 높게가지는 pop의 부담을 덜어서 모든 연산이 각각 O(1)에 할수있게 하는 것이다. 여기서 멀티팝이 O(k)이어야하는데, 우리는 push 연산만 하면 되니까 O(1)이 된다.
| 문제 2: amortized analysis을 사용하여 상각 비용을 계산합니다. 1) 먼저 AddLast()를 청구할 금액과 RemoveThirds()를 청구할 금액을 알려줍니다 2) 다음은 이러한 비용을 사용하여 이러한 작업의 실제 비용을 지불하는 방법을 보여줍니다. 3) 마지막으로 작업당 상환 비용을 기록합니다. AddLast는 4달러, RemoveThirds는 0달러를 지불합니다. 그런 다음 AddLast에 1달러를 사용하고 나머지 3달러를 저장한 다음 RemoveThirds에 3달러를 나중에 사용합니다. Remove Thirds에 대한 비용을 지불하기 위해 삭제된 각 항목에서 $3를 받습니다. n/3개의 항목이 삭제되어 $n이 삭제되었으므로 이 작업을 수행할 수 있습니다. 따라서 Remove Thirds(제3자 제거)가 끝날 때에도 목록에 남아 있는 모든 요소에는 $3가 여전히 저장되어 있습니다. 따라서 각 함수당 amortized cost는 O(1) |
0 1 2 /3 4 5 /6 7 8 : removethird 1번 실행되면 3$, 0 1/ 3 4 / 6 7 걔네들도 potantional $로 각 3달러가 저장되어 있다. 따라서 O(1)이다.
시간복잡도
기본연산의 횟수 (ex. 정렬이라면 비교연산, 최대공약수는 나누는 횟수)
Divide-and-Conquer: 원소가 하나가 될 때까지 나눈 후 합침
분할: 문제를 여러 개의 부분 문제로 나눈다.
정복: 각 부분 문제를 재귀적으로 해결한다.
결합: 부분 문제들의 해를 결합한다.
1. 이진탐색 => ʘ(logn), 절반씩 탐색해서 key값을 찾아내니까 트리의 높이에 따라 시간복잡도가 달라진다.
2. 최댓값 찾기 => ʘ(n), 분할로 풀경우, 오른쪽과 왼쪽에 2T(n-1)이고 그 둘을 최종비교하는 연산에 1이 추가된다.
3. 두 n-bit의 정수 곱셈:
방법1- 곱하는 수의 각 bit에 대해 이동연산을 진행한다. 첫 과정에서는 0번, 두번째 과정에서는 1번, n번째 과정에서는 n-1의 이동연산이 필요하다. 즉 이 부분은 O(1)+O(2)+O(3)+..O(n-1)=O(n^2)이 나온다. 이동 연산을 끝낸 후에는 최대 2n-bit로 이루어진 숫자 n개에 대해 add연산을 해야한다. 하번의 덧셈과정에서는 2번의 비트연산이 최대 2n번 필요하므로 O(n)이다. 그러므로 덧셈에 필요한 시간복잡도는 (n-1)*O(n) = O(n^2)이다. 곱셈에 필요한 총 시간복잡도는 O(n^2)이다.
방법2-
4. merge sort: 병합 단계의 높이 각 단계에서 정렬에 필요한 반복 횟수는
5. quick sort:
6. 행렬 곱셈:
Dynamic Programming
:이전값을 테이블에 저장해두고 큰문제를 풀때 이용
1. LIS: 만약 주어진 수열의 모든 부분집합을 다고려하면, 부분집합 공식에 의해 O(2^n)의 시간복잡도가 걸린다.
하지만 다이나믹 프로그래밍으로 풀면, 증가 부분 수열의 최댓값 => O(n^2), 각 hi를 찾기 위해 ai와 그 앞에 있는 (i-1)개의 원소들과 비교해야 하니까 for문이 두개 들어가기 때문이다.
2, 이전값과 비교하는 이중for문에서 전체시간복잡도가 구해지는데,
O(n^2)인 이유?
2. 연속 행렬 곱셈 순서: 하나씩 다구하면 지수함수 시간복잡도가 나온다.
행렬을 곱할 때, 최소 원소 곱셈의 수(다 더하는 것)와 곱셈 순서를 구하는 문제
m11, m22, m33, m44는 0
곱셈의 수(A*B, B*C, C*A..) 를 저장해두면 빨리 구할 수 있음 =>
3. Warshall-Floyd's algorithm: 모든 쌍 최단 경로와 가중치를 구하는 문제(다이케스트라로도 풀 수있으나 더 간단)
D(k)에서 k는 k를 통과해서 갈 수 있는 최단거리이다. 따라서 k=0이면 통과할 수 있는 정점이 없다는 것이다.
4. 0-1 knapsack problem
Greedy Algorithm(프림,크루스칼,다이케스트라 굿굿)
1. chained matrix multiplications: 다이나믹으로 푸는게 정확
2. 최소 스패닝 트리(프림 알고리즘과 크루스칼 알고리즘): 모든 정점들을 잇는 간선의 가중치를 최소화할 것
프림이 더 짧은 거리있으면 그걸로 대체, 아니면 유지
- 크루스칼 알고리즘은 간선의 개수가 E개일 때, 가중치에 따라 간선을 정렬해야해서 O(ElogE)의 시간복잡도를 갖는다.
- 프림 알고르짐은 매 정점마다 현재 노드로부터의 거리가 최소가 되는 v_min을 찾기 위해서 O(V^2)의 시간복잡도를 갖는다.
3. 분수배낭꾸리기: 배낭의 최대용량과 물건의 무게와 이윤이 주어졌을 때, 이윤을 최대화시키도록 가방을 채울 것
우리가 보는건 fractional knapsack(물건 쪼개기 가능) , 단위무게당 이윤을 큰것부터 정렬해놔야 해서 총 시간복잡도는 ʘ(nlogn)
4. 허프만 코드: 빈도수가 적은 문자를 차례로 알아내려고 최소 힙써서 우선순위 큐 구현,
- 각 빈도수를 노드에 저장할 때 O(n) 시간이 걸린다.
- 우선순위 큐로 힙 자료구조를 사용하면 O(n) 시간이 걸린다.
- 루프는 (n - 1)번 반복된다.
- 큐에서 최소 빈도수 노드 2개를 삭제 후 새 노드를 큐에 다시 삽입하는 과정에서 O(logn)이 걸린다.
- 즉 루프의 시간 복잡도는 O(nlogn)이다.
- 따라서 허프만 코딩의 시간 복잡도는 O(nlogn)이다.
NP