일정한 상각 시간

Question

알고리즘의 시간 복잡성에 대해 이야기 할 때 "일정한 상각 시간"이란 무엇입니까?

Answer 1

간단한 용어로 설명 된 상각 시간 :

작업을 수행하는 경우 백만 번 말하면 최악의 상황이나 해당 작업의 최상의 사례에 신경 쓰지 않습니다. .

따라서 "한 번에 한 번"이 속도를 희석하기에 충분히 드물다면 작동이 한 번에 매우 느려지는 경우는 중요하지 않습니다. 본질적으로 상각 시간은 "많은 작업을 수행하는 경우 작업 당 평균 시간"을 의미합니다. 상각 시간이 일정 할 필요는 없습니다. 당신은 선형 및 로그 상각 시간을 가질 수 있습니다.

새로운 항목을 반복적으로 추가하는 동적 배열에 대한 Mats의 예를 들어 보겠습니다. 일반적으로 항목을 추가하는 데 일정한 시간이 걸립니다 (즉, 즉, O(1)). 그러나 배열이 가득 차면 공간을 두 배나 많은 공간을 할당하고 데이터를 새 지역으로 복사 한 후 이전 공간을 제거합니다. 일정한 시간에 할당되고 자유롭게 운행한다고 가정하면이 확대 과정은 O(n) N이 배열의 현재 크기 인 시간.

따라서 확대 할 때마다 마지막 확대보다 약 2 배의 시간이 걸립니다. 그러나 당신은 또한 그것을하기 전에 두 번 기다렸다! 따라서 각 확대 비용은 삽입 중에 "확산"될 수 있습니다. 이것은 장기적으로 추가에 걸리는 총 시간이 중 배열에 항목이 있습니다 O(m), 그리고 따라서 상각 된 시간 (예 : 삽입 당 시간)은 O(1).

Answer 2

이는 시간이 지남에 따라 최악의 시나리오가 기본적으로 O (1) 또는 일정한 시간으로 기본값을 제공한다는 것을 의미합니다. 일반적인 예는 동적 배열입니다. 새 항목에 이미 메모리를 할당 한 경우 O (1)을 추가하면 추가됩니다. 우리가 그것을 할당하지 않으면 우리는 현재 금액의 두 배를 할당함으로써 그렇게 할 것입니다. 이 특별한 삽입 ~ 아니다 O (1)이 아니라 다른 것입니다.

중요한 것은 알고리즘이 일련의 연산 후에 고가의 작업이 상각되어 전체 작업 O (1)를 렌더링 할 것을 보장한다는 것입니다.

또는 더 엄격한 용어로

상수 C가 있습니다 모든 일련의 운영 (또한 비용이 많이 드는 작동으로 끝나는 하나) 길이 L, 시간은 c*l보다 크지 않습니다 (감사합니다. Rafał Dowgird)

Answer 3

직관적 인 사고 방식을 개발하려면 요소 삽입을 고려하십시오. 동적 배열 (예를 들어 std::vector C ++). 그래프를 플로팅하여 배열에 n 요소를 삽입하는 데 필요한 작업 수 (y)의 종속성을 보여줍니다.

검은 그래프의 수직 부분은 배열을 확장하기 위해 메모리의 재 할당에 해당합니다. 여기서 우리는이 의존성이 대략 선으로 표시 될 수 있음을 알 수 있습니다. 그리고이 라인 방정식입니다 Y=C*N + b (C 일정하고 b 우리의 경우 = 0). 그러므로 우리는 우리가 지출해야한다고 말할 수 있습니다 C*N 배열에 n 요소를 추가하기 위해 평균적으로 작업 또는 C*1 하나의 요소를 추가하기위한 작업 (상각 일정한 시간).

Answer 4

3 번 반복 읽기 후 Wikipedia 설명이 유용하다는 것을 발견했습니다.

원천: https://en.wikipedia.org/wiki/amortized_analysis#dynamic_array

"동적 배열

동적 배열에 대한 푸시 작동의 상각 된 분석

Java의 Arraylist와 같이 더 많은 요소가 추가되면 크기가 증가하는 동적 배열을 고려하십시오. 우리가 동적 인 크기 4의 배열로 시작했다면, 4 가지 요소를 밀어 넣는 데 일정한 시간이 걸립니다. 그러나 5 번째 요소를 해당 배열로 밀면 배열이 현재 크기의 두 배의 배열 (8)을 생성하고 이전 요소를 새 배열에 복사 한 다음 새 요소를 추가해야하므로 더 오래 걸립니다. 다음 3 개의 푸시 작업은 비슷하게 일정한 시간이 걸리며, 후속 추가에는 배열 크기의 또 다른 느린 배가가 필요합니다.

일반적으로 크기 n 배열로의 임의의 푸시 n을 고려하면 푸시 작업이 크기의 두 배가 작동을 수행하는 데 시간이 걸리는 마지막 시간을 제외하고 일정한 시간이 걸린다는 것을 알 수 있습니다. N 작업이 N 작업이 있었기 때문에이 평균을 취하고 요소를 동적 배열로 푸시하는 데 O (N/N) = O (1), 일정한 시간을 찾을 수 있습니다. "

간단한 이야기로서 이해하기 위해 :

돈이 많다고 가정합니다. 그리고 당신은 그들을 방에 쌓아 놓고 싶습니다. 그리고 당신은 현재 또는 미래에 필요한만큼 긴 손과 다리를 가지고 있습니다. 그리고 한 방에 모두 채워야하므로 잠그기 쉽습니다.

그래서 당신은 방의 끝/ 모서리로 가서 쌓기 시작합니다. 당신이 그들을 쌓을 때, 천천히 방은 공간이 부족합니다. 그러나 채우면서 쉽게 쌓을 수있었습니다. 돈을 얻었고 돈을 넣으십시오. 쉬운. O (1)입니다. 우리는 이전 돈을 옮길 필요가 없습니다.

일단 방은 공간이 부족합니다. 더 큰 다른 방이 필요합니다. 여기에는 문제가 있습니다. 우리는 단 1 개의 방만 가질 수 있으므로 1 개의 잠금 만 가질 수 있기 때문에 그 방에있는 기존의 모든 돈을 새로운 더 큰 방으로 옮겨야합니다. 따라서 모든 돈을 작은 방에서 더 큰 방으로 옮기십시오. 즉, 모두 다시 쌓으십시오. 따라서 우리는 이전의 모든 돈을 모두 옮겨야합니다. 따라서 O (N)입니다. (N이 이전 돈의 총 돈이라고 가정)

다시 말해서, 단지 1 개의 작업만이되기 쉬웠지만 더 큰 방으로 이동해야 할 때는 N 운영을 수행했습니다. 다시 말해, 평균이라면 처음에는 1 개의 삽입, 다른 방으로 이동하는 동안 1 개 더 움직입니다. 총 2 개의 작업, 하나의 삽입, 하나의 이동.

N이 작은 방에서도 백만처럼 크다고 가정하면 N (백만)에 비해 2 개의 작업은 실제로 비슷한 숫자가 아니므로 일정하거나 O (1)으로 간주됩니다.

우리가 위의 모든 것을 다른 더 큰 방에서 할 때를 가정하고 다시 움직여야합니다. 여전히 동일합니다. N2 (예 : 10 억)은 더 큰 방에서 새로운 금액의 돈입니다.

그래서 우리는 N2를 가지고 있습니다 (여기에는 작은 방에서 더 큰 방으로 이동 한 이후 이전의 N 포함).

우리는 여전히 2 개의 작업 만 필요하며, 하나는 더 큰 방에 삽입 한 다음 다른 이동 작업은 더 큰 방으로 이동합니다.

따라서 N2 (10 억)의 경우에도 각각 2 개의 작업입니다. 다시는 아무것도 아닙니다. 따라서 일정하거나 O (1)

따라서 N이 N에서 N2로 증가함에 따라 크게 중요하지 않습니다. 여전히 일정하거나 각각의 n에 필요한 O (1) 작업이 필요합니다.

---

이제 N은 1, 매우 작고 돈의 수가 작고, 아주 작은 방이 있으며, 이는 단 1 카운트의 돈에 불과합니다.

방에 돈을 채우 자마자 방이 채워집니다.

더 큰 방에 갈 때는 총 2 건의 돈 만 더 잘 맞을 수 있다고 가정합니다. 즉, 이전은 돈과 1이 더 움직였습니다. 그리고 다시 채워졌습니다.

이런 식으로 N은 천천히 성장하고 있으며, 우리는 이전 방에서 모든 돈을 옮기고 있기 때문에 더 이상 일정한 O (1)가 아닙니다.

100 번 후에, 새로운 방은 이전에서 100 번의 돈을, 그리고 수용 할 수있는 1 개의 돈을 더 적합합니다. 이것은 O (n)입니다. O (n+1)은 O (n)이기 때문에, 즉 100 또는 101의 정도는 동일하며, 이전 이야기와는 반대로 수백 수백만, 수십억에 이르는 것과는 반대로 수백입니다. .

따라서 이것은 우리의 돈 (변수)에 실내 (또는 기억/ 램)를 할당하는 비효율적 인 방법입니다.

---

따라서 좋은 방법은 2의 힘으로 더 많은 공간을 할당하는 것입니다.

첫 번째 방 크기 = 1의 돈에 맞습니다
두 번째 방 크기 = 4 횟수에 적합합니다
3rd room size = 8의 돈에 맞습니다
4 번째 객실 크기 = 16 횟수에 적합합니다
5 번째 방 크기 = 32의 돈에 맞습니다
6 번째 객실 크기 = 64의 돈에 적합합니다
7 번째 객실 크기 = 128의 돈에 적합합니다
8 번째 객실 크기 = 256의 돈에 적합합니다
9 번째 객실 크기 = 512의 돈에 적합합니다
10 번째 방 크기 = 1024 돈에 맞습니다
11 번째 방 크기 = 2,048의 돈에 적합합니다
...
16 번째 방 크기 = 65,536의 돈에 적합합니다
...
32 번째 객실 크기 = 4,294,967,296 돈에 적합합니다
...
64 번째 객실 크기 = 18,446,744,073,709,551,616 돈에 적합합니다

이것이 왜 더 나은가? 처음에는 천천히 자라며 나중에 더 빨리 자라기 때문에 RAM의 기억의 양과 비교할 때.

첫 번째 경우에는 돈 당 처리해야 할 총 작업량이 고정되어 있고 (2) 실내 크기 (N)와 비슷하지 않기 때문에 초기 단계에서 취한 방도 가능하기 때문에 이것은 도움이됩니다. 우리가 첫 번째로 저축하기 위해 많은 돈을 벌 수 있는지에 따라 완전히 사용할 수 없다는 큰 (백만).

그러나 마지막 경우, 2의 힘은 램의 한계에서 자랍니다. 따라서 2의 전력이 증가하면 무장 한 분석은 일정하게 유지되며 오늘날 우리가 가지고있는 제한된 RAM에 친숙합니다.

Answer 5

위의 설명은 골재 분석에 적용되는데, 이는 여러 작업에 대한 "평균"을 취한다는 아이디어입니다. 나는 그들이 은행가-방법 또는 물리학자가 상각 된 분석의 방법에 어떻게 적용되는지 잘 모르겠습니다.

지금. 정답이 정확히 확신하지 못합니다. 그러나 그것은 물리학 자+은행가의 방법의 원칙 조건과 관련이 있습니다.

(운영의 상각 된 비용의 합)> = (실제 작업의 합계).

내가 직면 한 주요 어려움은 상각 된-상징적 수술 비용이 정상-상징적 비용과 다르다는 점을 감안할 때 상각 된 비용의 중요성을 평가하는 방법을 잘 모르겠다는 것입니다.

그때 누군가가 상각 된 비용을주는 경우, 나는 그것이 정상-상징적 비용과 동일하지 않다는 것을 알고 있습니다.

우리는 다른 작업이 저하되는 동안 일부 작업이 과충전 된 경우가 있기 때문에, 하나의 가설은 개별 운영의 상각 된 비용을 인용하는 것이 의미가 없다는 것입니다.

예를 들어 : 피보나키 힙의 경우, "힙의 잠재력을 증가시키는 초기 작업으로 수행 된 작업에 의해 비용이 줄어든다"는 비용이 절감되기 때문에 비용을 O (1)로 감소시키는 상각 비용을 인용하는 것은 의미가 없다.

또는

우리는 다음과 같이 상각 된 비용에 대한 이유가 있다는 또 다른 가설을 가질 수 있습니다.

1. 고가의 작업에는 여러 저렴한 작업이 진행될 예정입니다.

2. 분석을 위해, 나는 그들의 점근 기간이 변하지 않도록 약간의 저렴한 작업을 과도하게 충전 할 것입니다.

3. 이러한 저렴한 작업이 증가함에 따라 값 비싼 운영에 더 적은 점근 비용이 있음을 증명할 수 있습니다.

4. 따라서 나는 N 운영 비용의 점근적으로 향상/감소했다.

따라서 상각 된 비용 분석 + 상각 된 비용 바운드는 이제 고가의 작업에만 적용됩니다. 저렴한 작업은 정상-상징적 인 비용과 동일한 점근 적 아모르트 비용을 가지고 있습니다.