일반적인 동적 배열 구현에서 새 요소를위한 공간이 없을 때 스택을 두 배로 만듭니다. 이 두 배의 경우 푸시 조작의 평균 시간은 O (n)입니다.스택의 동적 배열 구현을위한 복잡성
두 배가되는 대신에 (n + k)만큼 스택 크기를 늘린 것은 무엇입니까? 그 스택이 비어 가정
을 따르며, K = 10, 우리는 (10 개)에 소자 스택을 늘리면
내 접근법이다. 10 개의 요소 뒤에는 20 개의 요소가 있습니다. 주변 요소를 복사
평균 시간에 대한 푸시
그래서 평균 시간은 O (N)의 순서로해도 ... 10 + 20 + 30 +입니까?
제 접근 방법이 맞습니까?
저장 용량을 늘리는 방법에 따라 k는 충분히 작습니다. 모든 경우 또는 다른 경우 O (1) 일 수 있습니다.
'관리되는 언어에서, n + k 크기의 새 배열을 만든 다음 크기가 n 인 이전 배열을 새로운 것으로 복사하고 마지막으로 이전의 참조를 대체합니다. 새 배열로 배열하십시오. 그것은 O (1) (배열 생성, 가정) + O (n) (데이터 복사) + O (1) (참조 변경)입니다. 매우 구현에 의존하기 때문에 우리는 가비지 수집기 실행을 무시합니다. 관리되지 않는 언어에서는 realloc과 비슷한 것을 사용할 수 있으므로 새로운 요소가 동일한 메모리 영역을 차지하고 필요한 항목의 수만 확장되므로 복사 할 필요없이 이전 요소가 보존됩니다. 이 경우 모든 경우에 O (1)입니다. 그러나 때로는 메모리 조각화로 인해 저장소를 필요한 항목 수로 확장하는 것이 불가능하므로 관리되는 언어와 같은 방식이 사용됩니다 (단, realloc 구현을 통해 암시 적으로 수행됩니다). 이 경우 복잡성은 관리되는 언어와 동일합니다. O (n).
실용적인 관점에서 볼 때 대답입니다. 위의 대답을 사용하여 분석적 관점에서 대답을 찾을 수 있기를 바랍니다. 행운을 빕니다.
계산이 올바르지 않습니다. 동적 배열의 일반적인 구현이 크기를 두 배로 늘리는 (또는 더 일반적으로 x 퍼센트로 크기를 늘리는) 이유가 있습니다.
는 1부터 n까지 크기가 증가하는 경우 (2) = I하면 1 + 2 + 4 + 8 + 16 + ... + 2 I 인 복사 소자의 총량. 이 값을 합하면 2 i + 1보다 작으므로 총 시간 복잡도는 O (n)이고 한 삽입의 amortized time complexity은 O (1)입니다. n이 2의 거듭 제곱이 아니면 연산은 약간 더 복잡해 지지만 결과는 동일합니다.
한편, 크기를 k, 0에서 n = i * k로 늘리면 복사하는 요소의 총량은 k + 2k + 3k + ... + ik가됩니다. 이 값을 합하면 (ik + k) * (ik/k)/2 = O (n)가됩니다. 그리고 하나의 삽입의 상환 된 복잡성은 O (n)이 될 것입니다.
이 때문에 솔루션이 크기가 두 배가되는 것보다 훨씬 더 나쁩니다.