归并排序算法效率

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、数组位置分配和迭代）。他简化了这个，我相信是为了class，到6n。
这一切对我来说都很有意义，我的问题来自我正在执行的实现以及它如何影响算法以及它可能添加的一些 tradeoffs/inefficiencies 。

下面是我在 swift 中使用 playground 的代码：

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)

我的问题如下：

merge<T:Comparable> 函数开头的 guard 语句是否真的降低了效率？考虑到我们总是将数组减半，它唯一适用的情况是基本情况以及数组中的项目数为奇数时。
这对我来说似乎实际上会增加更多的处理并提供最小的 return 因为它发生的时间是我们将数组减半到没有项目的点。
关于我在合并中的 if 语句。由于它要检查多个条件，这是否会影响我编写的算法的整体效率？如果是这样，对我来说，效果似乎会根据它何时会突破 if 语句（例如，在第一个条件或第二个条件下）而有所不同。
这是在分析算法时要重点考虑的事情吗？如果是，当它从算法中爆发时，您如何解释方差？

任何其他 analysis/tips 如果您能提供我所写的内容，将不胜感激。

Answer 1

您很快就会了解 Big-O 和 Big-Theta，您并不关心确切的运行时间（相信我，我很快就会说非常，就像在一两次讲座中一样）。在那之前，这是你需要知道的：

是的，守卫需要一些时间，但每次迭代的时间都是相同的。因此，如果在没有守卫的情况下每次迭代花费 X 时间，而你执行 n 函数调用，那么总共需要 X*n 时间。现在添加在每次通话中花费 Y 时间的守卫。您现在总共需要 (X+Y)*n 时间。这是一个常数因子，当 n 变得非常大时，与 n 因子相比，(X+Y) 因子变得可以忽略不计。也就是说，如果您可以将函数 X*n 减少到 (X+Y)*(log n)，那么增加 Y 的工作量是值得的，因为您总共进行了更少的迭代。
同样的道理也适用于你的第二个问题。是的，检查“如果 X 或 Y”比检查“如果 X”花费更多时间，但它是一个常数。额外时间不随n.
的大小变化

在某些语言中，如果第一个条件失败，您只检查第二个条件。我们如何解释这一点？最简单的解决方案是认识到比较次数的上限将是 3，而迭代次数可能是数百万，并且 n 很大。但是 3 是一个常数，所以它每次迭代最多增加一个常数的工作量。您可以进入 nitty-gritty 细节并尝试推断第一个、第二个和第三个条件为真或假的频率分布，但通常您并不想沿着这条路走下去。假装你总是做所有的比较。

所以是的，如果您执行与以前相同的迭代次数，则添加守卫可能对您的运行时不利。但有时在每次迭代中添加额外的工作可以减少所需的迭代次数。

归并排序算法效率

Merge Sort algorithm efficiency

sorting

algorithm

mergesort

swift