큰 오 표기법 - 푸시 및 팝

Question

나는 커다란 오 표기법 뒤에있는 이론을 이해하기 시작했다. 즉, 함수 속도가 커지는 속도를 측정하는 방법이다. 다시 말해, Big O는 알고리즘의 효율성을 정량화합니다. 그러나 그것의 구현은 다른 것입니다.

예를 들어 최상의 경우 시나리오에서 스택에서 제거하거나 스택에 추가하는 데 걸리는 단계 수가 고정되기 때문에 푸시 및 풀 작업은 O (1)이됩니다. 가치에 관계없이 프로세스는 동일합니다.

푸시 및 팝과 같은 일련의 이벤트로 인해 O (1)에서 O (n^2)로 성능이 저하 될 수 있습니다. n/2 용량의 배열, n 개의 밀어 넣기 및 팝하는 작업, 전체 또는 절반 꽉 채워진 상태에서 용량을 두 배 또는 반으로 줄이는 동적 배열이있는 경우 이러한 작업이 발생하는 순서가 속도에 영향을 미칠 수 있습니다. 어떤 프로그램이 완료 되었습니까? push와 pop이 스택의 최상위 요소에서 작동하기 때문에 효율성이 상수에서 O (n^2)로 어떻게 이동하는지 보는 데 어려움을 겪고 있습니다. 사전에

감사합니다.

Answer 1

링크 된 목록으로 스택을 구현하면 푸시 및 팝은 항상 일정 시간 (예 : O (1))이됩니다.

스택에 동적 배열 구현을 선택하지 않을 것입니다. 런타임에 문제가되지 않는 한, 동적 배열을 사용할 준비가되어 있고 사용할 수있게되어서 더 효율적이지 않았습니다. 스택 구현이 편리하다. 그러나 전체 또는 절반 빈 때 각각 위아래로 크기가 조정 된 배열을 사용했다면 해당 런타임은 O (1)이고 푸시 및 팝 수는 크기가 작고 O (n) 크기가있을 때 (따라서 전반적인 O (n)).

스택으로 사용되는 동적 배열이 구현에 버그가없는 한 O (n^2)만큼 성능이 나쁜 경우를 생각할 수 없습니다.

Answer 2

동적 배열이 크기 조정 작업을 매우 지능적으로 처리한다고 가정합니다. 그러나 이것이 사실이 아니라면, O (n^2) 런타임으로 끝날 수도 있습니다. 배열이 가득 차면 크기가 두 배로 늘어나지 않지만 단순히 크기가 + 1로 조정됩니다. 또한 크기가 1부터 시작한다고 가정 해 보겠습니다. O (1)에 첫 번째 요소를 삽입합니다. 두 번째 요소를 삽입 할 때 배열의 크기를 2로 변경해야 이전 값을 복사해야합니다. 요소 k를 삽입 할 때 현재 크기 k-1을 가지며 크기 k로 크기를 조정해야 k-1 개의 요소를 복사해야합니다.

따라서 n 개의 요소를 삽입하려면 배열을 n-1 번 복사하면됩니다. O (n) resizes. 더 많은 요소가 삽입 될수록 더 많은 복사가 필요하기 때문에 복사 작업은 n에 선형 적으로 종속됩니다. 크기 조정 당 O (n) 개의 사본. O (n * n) = O (n^2)가 런타임 복잡성으로 나타납니다.