Дать рекуррентное уравнение

Question

я путать о том, где второе слагаемое [Т (п) = 2T (п/2) + ТЭТА (п)] является производным от при написании рекуррентного уравнения для сортировки слияниями.

Из класса Coursera было указано, что второй член обусловлен тем, что происходит за пределами рекурсивных вызовов. Так что я думаю, потому что это связано с 2 Для Loops, каждый из них будет идти до п/2, так что общее будет считать до п:

function mergesort(m) 
    var list left, right 
    if length(m) ≤ 1 
     return m 
    else 
     middle = length(m)/2 
     for each x in m up to middle 
      add x to left 
     for each x in m after middle 
      add x to right 
     left = mergesort(left) 
     right = mergesort(right) 
     result = merge(left, right) 
     return result 

Любая помощь будет оценена. Thanks

Answer 1

Да, это так. Существует линейная работа, выполняемая для итерации по элементам входного списка, распределения каждого элемента в левый или правый подмассивы. Это объясняет термин «Θ (n)» в повторении.

Надеюсь, это поможет!