Эффективность алгоритма сортировки Merge

Question

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

В этом случае алгоритм, который мы рассматривали, является алгоритмом сортировки слиянием. После получения псевдокода мы также проводим анализ алгоритма для времени выполнения против n числа элементов в массиве. После быстрого анализа учитель прибыл в 6nlog(base2)(n) + 6n в качестве приблизительного времени выполнения алгоритма.

Псевдокод дано было для слияния части только алгоритма и задается следующим образом:

C = output [length = n] 
A = 1st sorted array [n/2] 
B = 2nd sorted array [n/2] 
i = 1 
j = 1 
for k = 1 to n 
    if A(i) < B(j) 
     C(k) = A(i) 
     i++ 
    else [B(j) < A(i)] 
     C(k) = B(j) 
     j++ 
    end 
end 

Он в основном сделал пробой выше принимая 4n+2 (2 для деклараций i и j, и 4 для количества выполненных операций - for, if, назначение позиции массива и итерация). Он упростил это, я считаю, ради класса, до 6n.
Все это имеет смысл для меня, мой вопрос возникает из реализации, которую я выполняю, и как она влияет на алгоритмы и некоторые компромиссы/неэффективность, которые она может добавить.

Ниже мой код в стрижа, используя площадку:

func mergeSort<T:Comparable>(_ array:[T]) -> [T] { 
    guard array.count > 1 else { return array } 

    let lowerHalfArray = array[0..<array.count/2] 
    let upperHalfArray = array[array.count/2..<array.count] 

    let lowerSortedArray = mergeSort(array: Array(lowerHalfArray)) 
    let upperSortedArray = mergeSort(array: Array(upperHalfArray)) 

    return merge(lhs:lowerSortedArray, rhs:upperSortedArray) 
} 

func merge<T:Comparable>(lhs:[T], rhs:[T]) -> [T] { 
    guard lhs.count > 0 else { return rhs } 
    guard rhs.count > 0 else { return lhs } 

    var i = 0 
    var j = 0 

    var mergedArray = [T]() 
    let loopCount = (lhs.count + rhs.count) 
    for _ in 0..<loopCount { 
     if j == rhs.count || (i < lhs.count && lhs[i] < rhs[j]) { 
      mergedArray.append(lhs[i]) 
      i += 1 
     } else { 
      mergedArray.append(rhs[j]) 
      j += 1 
     } 
    } 

    return mergedArray 
} 

let values = [5,4,8,7,6,3,1,2,9] 
let sortedValues = mergeSort(values) 

Мои вопросы для этого следующие:

1. Выполните guard заявления в начале функции merge<T:Comparable> на самом деле это сделать более неэффективно? Учитывая, что мы всегда сокращаем половину массива, единственный раз, когда он будет считаться истинным, будет для базового случая и когда в массиве будет нечетное количество элементов.
   Это похоже на то, что на самом деле это добавит больше обработки и даст минимальный доход с момента, когда это произойдет, когда мы вдвое уменьшим массив до точки, в которой нет элементов.

2. Относительно моего if заявление в слиянии. Поскольку он проверяет несколько условий, влияет ли это на общую эффективность алгоритма, который я написал? Если это так, эффекты для меня кажутся такими, что они меняются в зависимости от того, когда он вырвется из инструкции if (например, в первом условии или во втором).
   Это что-то, что считается тяжелым при анализе алгоритмов, и если да, то как вы объясняете дисперсию, когда она выходит из алгоритма?

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

Answer 1

Вскоре вы узнаете о Big-O и Big-Theta, где вам не нужны точные времена работы (поверьте мне, когда я скажу очень скоро, как в лекции или два). До тех пор, это не то, что вам нужно знать:

1. Да, охранники занять некоторое время, но это одно и то же количество времени в каждой итерации.Поэтому, если каждая итерация принимает X количество времени без охраны, и вы делаете n вызовы функций, тогда требуется X*n всего времени. Теперь добавьте в guars, которые принимают Y количество времени в каждом вызове. Теперь вам нужно всего (X+Y)*n раз. Это постоянный коэффициент, и когда n становится очень большим, коэффициент (X+Y) становится пренебрежимым по сравнению с фактором n. То есть, если вы можете уменьшить функцию X*n до (X+Y)*(log n), то стоит добавить Y количество работы, потому что вы выполняете меньше итераций в целом.

2. Те же соображения применимы к вашему второму вопросу. Да, проверка «если X или Y» занимает больше времени, чем проверка «если X», но это постоянный фактор. Дополнительное время не зависит от размера n.

   На некоторых языках вы проверяете только второе условие, если первое не удается. Как мы это объясняем? Самое простое решение состоит в том, чтобы понять, что верхняя граница числа сравнений будет равна 3, а число итераций может быть потенциально миллионами с большим n. Но 3 - это постоянное число, поэтому он добавляет не более постоянного количества работы на итерацию. Вы можете вдаваться в подробные детали и попытаться объяснить, как часто первое, второе и третье условие будут истинными или ложными, но часто вы действительно не хотите идти по этой дороге. Представьте, что вы всегда делаете все сравнения.

Так что да, добавление охранников может быть плохим для вашей среды выполнения, если вы делаете то же количество итераций, что и раньше. Но иногда добавление дополнительной работы на каждой итерации может уменьшить количество требуемых итераций.