Найти сложность алгоритма рекурсивного журнала с полами и потолками

Question

У меня есть этот уродливый алгоритм (да, это курс компьютерной науки, поэтому он уродливый по назначению). Мы должны найти его сложность, используя разные методы. Один из методов - обратные замены. Просто взглянув на алгоритм, кажется очевидным, что его сложность будет где-то в диапазоне (log (n - m)), так как размер экземпляра делится на три на каждый рекурсивный вызов.

Function WeirdSort(Array[m..n]) 
    if (m < n) then 
     if (A[m] > A[n]) then 
      temp = A[m] 
      A[m] = A[n] 
      A[n] = temp 
     end if 
     if (m + 1 < n) then 
      index = floor((n - m + 1)/3) 
      WeirdSort(A[m..n - index]) 
      WeirdSort(A[m + index..n]) 
      WeirdSort(A[m..n - index]) 
     end if 
    end if 
end Function 

Но я пытаюсь понять, как я могу достичь этого ответа методом обратной подстановки. Более конкретно, я застрял в попытке разобраться с множеством floor() и потолка(), которые начинают отображаться для размера массива и как я должен иметь дело с ними.

Мой инстинкт говорит мне, что их нельзя просто отбросить, но, возможно, это то, что я должен делать?

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

Answer 1

Прошу прощения, но сложность далека от log(x).

Предположим, что в худшем случае, где m=1, что вы делаете, является рекурсией для 2/3 элементов 3 раза.

T(n) = 3*T(2n/3) + 1

Использование мастер theorm ==>T(n) = O(n^2.7~)