A(n) 유도.
스택 a의 상단 n개 원소를 다음과 같이 3개의 파티션으로 분할합니다. 이 때 분할의 기준이 되는 두 pivot값은 입력 원소를 0~n-1로 정규화 하는 것으로 쉽게 획득할 수 있습니다.
두 pivot값을 기준으로 얻은 3개의 파티션에 대하여 가장 큰 값들을 Big, 두 pivot값 사이의 값들을 Mid, 가장 작은 값들을 Small이라 하겠습니다. 각각의 파티션은 정렬되지 않았으며, 그 크기는 n/3으로 가능한 동일하게 유지합니다.
Big파트는 ra, Small파트는 pb, Mid파트는 pb + rb 커맨드가 필요합니다. 각 파티션의 크기가 n/3이므로, 도합 4n/3개의 커맨드가 필요합니다.
이 상황에서 rrr커맨드를 사용하여 Big과 Mid를 두 스택의 상단으로 한 번에 옮겨줍니다. 실제 상황에서는 n이 3의 배수가 아닐 수 있으므로, 위해서 Big과 Mid의 개수를 동일하게 맞춰줍니다.
도합 n/3개의 원소에 대하여 rrr을 수행했으므로, 그 비용은 n/3입니다.
여기서 a의 상단에 위치한 Big에 대하여 재귀적으로 정렬을 수행합니다. Big은 a상단에 n/3개 만큼 위치하므로, 그 비용은 **A(n/3)**입니다.
Mid에 대하여 재귀적으로 정렬하여 a의 상단으로 옮깁니다. Mid는 b의 상단에 n/3개만큼 존재하므로 그 비용은 **B(n/3)**입니다.
Mid와 마찬가지로 Small에 대해서도 재귀적으로 정렬 및 이동을 수행합니다. 비용은 B(n/3).
이상으로 a상단 n개 원소에 대한 정렬이 종료되었습니다. 각 과정을 거치면서 드는 비용을 총합하여 점화식 A(n)을 구하면 다음과 같습니다.
$$ A(n) = {5n\over 3} + A({n\over 3}) + 2 B({n\over 3}) $$
B(n) 유도.
A(n)과 유사하게 B(n)은 다음과 같이 수행됩니다.
3개의 파티션으로 분할, 그 비용은 4n/3.
Big 정렬, 비용은 A(n/3)
rrr커맨드를 이용하여 Mid와 Small 한 번에 상단으로 이동, 그 비용은 n/3.
Mid 정렬, 비용은 A(n/3)
Small을 정렬해서 a로 이동, 비용은 B(n/3)
이렇게 b의 상단의 n개 원소를 정렬하여 a의 상단으로 이동시켰습니다. 앞서 거친 단계들을 종합하면 다음과 같이 점화식을 얻을 수 있습니다.
$$ B(n) = {5n\over 3} + 2A({n\over 3}) + B({n\over 3}) $$