평신도의 관점에서 상각 된 복잡성?

평신도의 관점에서 상각 된 복잡성?

---

누군가가 평신도의 용어로 상각 된 복잡성을 설명 할 수 있습니까? 나는 온라인에서 정확한 정의를 찾는 데 어려움을 겪고 있으며 그것이 알고리즘 분석과 완전히 관련되는 방식을 모릅니다. 외부에서 참조하더라도 유용한 것은 무엇이든 높이 평가 될 것입니다.

---

상각 복잡도는 일련의 작업에 대해 평가 된 작업 당 총 비용입니다.

아이디어는 전체 시퀀스의 총 비용을 보장하면서 개별 작업이 상각 된 비용보다 훨씬 더 비싸도록 허용하는 것입니다.

예 :
C ++의 동작 std::vector<>. 경우 push_back()는 미리 할당 된 값이 상기 벡터 크기가 커, 상기 할당 된 길이를 두배.

따라서 단일 을 실행하는 push_back()데 O(N)시간 이 걸릴 수 있습니다 (배열의 내용이 새 메모리 할당에 복사 됨).

그러나 할당 크기가 두 배가 되었기 때문에 다음 N-1호출 을 실행할 때 push_back()마다 O(1)시간이 걸립니다 . 따라서 총 N작업에는 여전히 O(N)시간 이 걸립니다. 따라서 작업 당 push_back()상각 된 비용 을 제공 합니다 O(1).

---

달리 명시되지 않는 한, 상각 된 복잡성은 모든 작업 순서에 대한 점근 적 최악의 경우 보증입니다. 이것은 다음을 의미합니다.

• 상각되지 않은 복잡성과 마찬가지로 상각 된 복잡성에 사용되는 big-O 표기법은 고정 된 초기 오버 헤드와 일정한 성능 요인을 모두 무시합니다. 따라서 big-O 상각 된 성능을 평가하기 위해 일반적으로 상각 된 작업 시퀀스가 ​​고정 된 시작 비용을 상각하기에 "충분히 길다"고 가정 할 수 있습니다. 특히, std::vector<>예를 들어, 실제로 N추가 작업 이 발생할지 여부에 대해 걱정할 필요가 없습니다 . 분석의 점근 적 특성은 이미 예상하고 있습니다.

• 임의 길이 외에 상각 분석은 비용을 측정하는 작업 순서에 대해 가정하지 않습니다 . 가능한 작업 순서 에 대한 최악의 경우 보장입니다 . 악의적 인 공격자에 의해 작업이 아무리 나쁘게 선택 되더라도 상각 된 분석은 충분히 긴 작업 시퀀스가 ​​상각 된 비용의 합계보다 지속적으로 더 많은 비용이 들지 않도록 보장해야합니다. 이것이 (정규 자로 구체적으로 언급되지 않는 한) "확률"과 "평균 사례"가 상각 분석과 관련이없는 이유입니다. 일반적인 최악의 경우 Big-O 분석보다 더 그렇습니다!

---

상각 분석에서 일련의 데이터 구조 작업을 수행하는 데 필요한 시간은 수행 된 모든 작업에 대해 평균화됩니다. 상각 분석은 확률이 관련되지 않는다는 점에서 평균 사례 분석과 다릅니다. 상각 분석은 최악의 경우 각 작업의 평균 성능을 보장합니다.

(Cormen et al., "Introduction to Algorithms"에서)

시간이 평균화되고 평균 사례 분석이 아니라는 점을 모두 표시하므로 약간 혼란 스러울 수 있습니다. 그래서 이것을 재정적 비유로 설명해 보겠습니다 (실제로 "상각"은 은행 및 회계와 가장 일반적으로 관련된 단어입니다).

복권을 운영하고 있다고 가정합니다. (추첨권을 사지 않고 바로 복권을 운영합니다.) 10 만장의 표를 인쇄하면 1 통화 단위로 판매됩니다. 이 티켓 중 하나는 구매자에게 40,000 통화 단위를 부여합니다.

이제 모든 티켓을 판매 할 수 있다고 가정하면 60,000 통화 단위 (판매액 100,000 통화 단위에서 상금 40,000 통화 단위를 뺀 금액)를 얻을 수 있습니다. 귀하에게 각 티켓의 가치는 0.60 통화 단위이며 모든 티켓에 대해 상각됩니다. 이것은 신뢰할 수있는 값입니다. 저축 할 수 있습니다. 티켓 판매에 지쳐서 누군가가 와서 각각 0.30 통화 단위로 판매하겠다고 제안한다면, 당신은 당신이 어디에 서 있는지 정확히 알고 있습니다.

복권 구매자의 경우 상황이 다릅니다. 구매자는 복권을 구매할 때 0.60 통화 단위의 예상 손실이 있습니다. 그러나 그것은 확률 적입니다. 구매자는 30 년 동안 매일 10 장의 복권을 구매할 수 있습니다 (10 만 장 이상). 또는 하루에 한 장의 표를 자발적으로 구입하여 39,999 통화 단위를 얻을 수 있습니다.

데이터 구조 분석에 적용하면 첫 번째 경우에 대해 이야기하고 있는데, 이러한 종류의 모든 작업에 대해 일부 데이터 구조 작업 (예 : 삽입)의 비용을 상환합니다. 평균 사례 분석은 모든 작업의 ​​총 비용을 계산할 수 없지만 단일 작업의 예상 비용에 대한 확률 적 분석을 제공 할 수있는 확률 적 작업 (예 : 검색)의 예상 값을 다룹니다.

상각 된 분석은 고비용 작업이 드문 상황에 적용되는 경우가 많으며 그럴 경우가 많습니다. 하지만 항상 그런 것은 아닙니다. 예를 들어, 두 개의 스택으로 구성된 선입 선출 (FIFO) 대기열 인 소위 "은행가 대기열"을 생각해보십시오. (이것은 고전적인 기능적 데이터 구조입니다. 변경 불가능한 단일 링크 노드에서 저렴한 LIFO 스택을 구축 할 수 있지만 값싼 FIFO는 그렇게 명확하지 않습니다). 작업은 다음과 같이 구현됩니다.

put(x):  Push x on the right-hand stack.
y=get(): If the left-hand stack is empty:
           Pop each element off the right-hand stack and
             push it onto the left-hand stack. This effectively
             reverses the right-hand stack onto the left-hand stack.
         Pop and return the top element of the left-hand stack.

지금, 나는의 상각 후원 주장 put하고 get있다 O(1), 나는 빈 큐와 시작 및 종료한다고 가정. 분석은 간단합니다. 저는 항상 put오른쪽 스택에, get왼쪽 스택에 있습니다. 그래서 옆에서 If절, 각각 putA는 push, 각각 getA는 pop둘있는, O(1). s와 s If의 패턴에 따라 절을 몇 번 실행할지 모르겠지만 모든 요소가 오른쪽 스택에서 왼쪽 스택으로 정확히 한 번 이동한다는 것을 알고 있습니다. 따라서 n s와 n s 의 전체 시퀀스에 대한 총 비용 은 n es, n s 및 n s입니다. 여기서 a 는 a입니다.putgetputgetpushpopmovemovepopa push: 즉, 2n 연산 (n puts 및 n gets)은 2n pushes 및 2n을 생성 pop합니다. 따라서 단일 put또는 의 상각 된 비용 get은 1 push과 1 pop입니다.

은행가의 대기열은 상각 된 복잡성 분석 (및 "상각 된"단어와 금융의 연관성) 때문에 정확하게 호출됩니다. 은행가의 대기열은 일반적인 인터뷰 질문에 대한 답입니다. 비록 지금은 너무 잘 알려져 있다고 생각합니다. 상각 된 O (1) 시간에 다음 세 가지 작업을 구현하는 대기열을 생각해보세요.

1) 대기열에서 가장 오래된 요소를 가져 와서 제거합니다.

2) 대기열에 새 요소를 넣고

3) 현재 최대 요소의 값을 찾으십시오.

---

"상각 된 복잡성"의 원칙은 당신이 그것을 할 때 어떤 것이 꽤 복잡 할 수 있지만, 그것은 매우 자주 수행되지 않기 때문에 "복잡하지 않은"것으로 간주된다는 것입니다. 예를 들어, 때때로 균형을 잡아야하는 바이너리 트리를 만드는 경우 ( 2^n삽입 할 때마다 한 번씩) 트리 균형을 맞추는 것은 매우 복잡하지만 n 개의 삽입마다 한 번만 발생합니다 (예 : 삽입 번호 256에서 한 번, 다음에 다시 512 번째, 1024 번째 등). 다른 모든 삽입에서 복잡도는 O (1)입니다. 예, n 삽입마다 O (n)이 필요하지만 1/n확률 일뿐입니다. 따라서 O (n)에 1 / n을 곱하고 O (1)을 얻습니다. 그래서 이것은 "O (1)의 암기 된 복잡성"이라고합니다. 더 많은 요소를 추가할수록 트리를 재조정하는 데 소요되는 시간이 최소화되기 때문입니다.

---

Amortized means divided over repeated runs. The worst-case behavior is guaranteed not to happen with much frequency. For example if the slowest case is O(N), but the chance of that happening is just O(1/N), and otherwise the process is O(1), then the algorithm would still have amortized constant O(1) time. Just consider the work of each O(N) run to be parceled out to N other runs.

The concept depends on having enough runs to divide the total time over. If the algorithm is only run once, or it has to meet a deadline each time it runs, then the worst-case complexity is more relevant.

---

It is somewhat similar to multiplying worst case complexity of different branches in an algorithm with the probability of executing that branch, and adding the results. So if some branch is very unlikely to be taken, it contributes less to the complexity.

---

Say you are trying to find the kth smallest element of an unsorted array. Sorting the array would be O(n logn). So then finding the kth smallest number is just locating the index, so O(1).

Since the array is already sorted, we never have to sort again. We will never hit the worst case scenario more than once.

If we perform n queries of trying to locate kth smallest, it will still be O(n logn) because it dominates over O(1). If we average the time of each operation it will be:

(n logn)/n or O(logn). So, Time Complexity/ Number of Operations.

This is amortized complexity.

I think this is how it goes, im just learning it too..

참고URL : https://stackoverflow.com/questions/15079327/amortized-complexity-in-laymans-terms