Как написать уравнение рекуррентности для этого алгоритма?

Question

Я в замешательстве с написанием уравнения повторения для алгоритма ниже, может ли кто-нибудь помочь мне сделать это?

Вот алгоритм:

ThreeSort(A{i..j]){ 
    n = j-i+1; // number of elements 
    if (n==1) return; 
    if (n==2) and (A[i] > A[j]) then swap A[i] with A[j] 
    else if (n > 2) { 
     third = round(n/3); 
     ThreeSort(A[i..j-third]); // sort first 2/3rds 
     ThreeSort(A[i+third..j]); // sort last 2/3rds 
     ThreeSort(A[i..j-third]); // sort first 2/3rds 
    } 
} 

Answer 1

Вы должны разделить массив на три части. Первая часть - A[i...i+third-1], вторая - A[i+third...i+2*third-1], а третья - A[i+2*third...j]. После сортировки

ThreeSort(A[i...i+third-1]); 
ThreeSort(A[i+third...i+2*third-1]); 
ThreeSort(A[i+2*third...j]); 

Вы должны объединить три части массива в один. Тройное слияние выглядит как бинарное слияние.

Answer 2

Это не ответ, но он слишком длинный, чтобы вписаться в область комментариев, поэтому я размещаю его здесь.

Ваш код является неправильным, если round() когда-либо заканчивается. Предположим, что n==5 и массив содержит элементы 6,5,3,2,1. Вы получаете third==2 то (потому что 5/3 = 1,666 ... получает округляется вверх), а затем три стадии суб-сортировочные переупорядочить массив:

3,5,6,2,1
3,5,1,2,6
1,3,5,2,6

Вы нуждаетесь в середине (перекрывающейся) части, по крайней мере равной по длине обеим боковым частям, поэтому ваш third не должен превышать n/3 для правильной сортировки. Это означает, что вам нужно trunc вместо round здесь.

Answer 3

Я не уверен, но я считаю, что рекурсивное уравнение для определения времени является сложность Т (п) = 3 * Т (п/3) + θ (1) и в соответствии с методом Master: Т (п) ∈ θ (n)