알고리듬 -mergesort space complexity구하는데 잘 아시는 분 계신가요?

Question

mergesort - space complexity 분석하는것 질문 -특정 문제를 풀기 위해서 (여기서는 sort를 하는 것) mergesort를 실행을 시켰을때에 얼마만큼의 메모리가 필요한지를 분석하는 거잖아요. 그러면 stack call에서 max로 필요한 memory 스페이스를 분석을 하는 건데.. 확인해보니 마지막으로 실행 시킨 merge가 가장 많은 space를 필요로 하더라고요. 근데 마지막으로 실행시킨 merge는 당연히 tree구조에서 2번째 (root mergesort를 1번이라고 할때에) level에 있고요. 함수를 호출할때마다 필요한 메모리 공간을 stack에 차지하게 되기는 하지만, stack call에 merge/merge sort함수 호출 단위로 넣었을때에는 단지 tree level로 stack call의 level을 애널라이즈할 수 있지만, 예를 들면은 tree level에서 3개의 level이 있는 경우 최대 stack call의 height은 3이다 (함수자체를 하나의 cell 단위로 하였을 경우, cell &#61; 3개 필요). 이렇게 해서 merge sort를 분석하면은 merge sort를 적용시킬 n개의 array사이즈의 stack의 cell단위 height은 (함수 단위로 할 경우; cell &#61; 1함수) n개의 array 사이즈를 아래 그림과 같이 tree구조로 표현했을때에는 ceil(log2 (n) &#43; 1) level이 되고 이 level이 stack의 height이 되니까.. 그래서 stack의 height은 O(logn)으로 표현을 하더라고요. 그 다음에 merge를 하는데 필요한 time complexity는 O(n)으로 표현해서 이를 더하던데 O(logn &#43; n) 그 다음에 dominating term이 n이니 O(n)이 time complexity라고 하더라고요.제가 이해한 방식으로 문제를 풀 경우 위의 내용과는 다른데, 왜 위의 방식으로 저렇게 푸는지가 이해가 안가네요. 저의 가장 많이 stack을 차지할 때에 마지막 merge를 하는거고, 이때는 총 constant space &#43; n(size of array)만큼의 space가 필요로 하게 되고요. 어차피 이 메모리 공간을 처리할 수있는 공간이 있으면 나머지 merge들은 충분히 처리할 수 있는거니 무시해도 되고. 그래서 contstant &#43; n이니 O(n)으로 space complexity를 표현할 수 있는 거고요. 제가 뭔가 잘못한 부분이 있는지, 아니면 강의에서 나온 문제 풀이 방식을 왜 저렇게 풀었는지 등 아시는 분은 의견 좀 주세요. 감사합니다.

마르세유1 · Accepted Answer

배운지너무오래된내용이긴한데O표현에서 &#43; logn 은 상수취급해서 사라지는거 아닌가여? 추가해보자면작성자님방식은 마지막 단계까지의 array를 구하기 위한 stack 메모리 공간에 대한 설명이 빠져있는것 같습니다.. 물론 상수화되서 사라질거같지만요

즐겁게공부중 · Answer

위의 그림에서 tree를 보면은 여러 ms들이 있잖아요. 그렇지만 이것들은 알고리듬을 보면은 어차피 constant space를 차지하고 (array 사이즈 자체에 비례하지 않으니), merge 자체는 호출한 Array의 사이즈 (p ~ r까지)의 사이즈만큼을 최소한 필요로 하게 되잖아요. 사실상 merge 알고리듬을 보더라도 최소 array의 size만큼의 space는 필요하고, 거기다가 extra로 infinite (굉장히 큰 수)를 Left array & right array에 저장하며 L & R array의 index 표현하는 그런 변수들도 선언하기는 하지만.. 이들은 array의 사이즈에 비례하지 않고 언제나 merge함수 호출 시에 필요로 하는 용량인데.. 즉, 변하지 않는 용량이란 거죠. 그렇다면 마지막 merge (A,1,3,6) 호출시에 stack이 가장 많이 쌓이니 이 함수 호출 시에 필요로 하는 용량만 확보한다면은 해당 문제를 풀기위해 실행되는 다른 recursive merge함수들은 처리가 될 수 있잖아요. 그렇다면은 stack에 쌓이는 양은 최대 n &#43; 어떤 constant값이 되는 거고요. constant값은 merge(A,1,6) 이를 실행했을 때에 stack에서 필요한 저장 공간이고 이는 array size n&#61; 6인 것 뿐만이 아닌 모든 array size에 동일하게 먹히는 내용아닌가요? (제가 보기에는 그런데). 즉 마지막 merge를 할 때에 가장 많은 stack 공간이 필요로 하고 이는 n &#43; constant값이 되고요. n은 size에 비례한 값이고, constant는 여러 변수들의 공간을 저장하는데 필요한 것들을 더한거고, 그리고 이는 array의 사이즈에 비례하지 않아서 즉 array 사이즈가 몇이 되었건 일정하다는 것이죠. 그래서 결국 O(n)으로 표현할 수 있는거고요.제가 이해한 내용으로는 이렇게 설명이 가능한데, 이거를 prove해줄 수 있는 분이 없나요?

알고리듬 -mergesort space complexity구하는데 잘 아시는 분 계신가요?

2개의 답변

#space 목록