swift - 归并排序算法效率

Question

我目前正在学习在线算法类(class)，其中老师不会给出解决算法的代码，而是提供粗略的伪代码。因此，在上网寻找答案之前，我决定自己尝试一下。

在这种情况下，我们正在研究的算法是合并排序算法。在给出伪代码后，我们还深入分析了针对数组中 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 .
这对我来说都是有意义的，我的问题源于我正在执行的实现以及它如何影响算法以及它可能增加的一些权衡/低效率。

下面是我使用 Playground 的 swift 代码:

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 时间全部的。现在添加在每次调用中花费 Y 时间的 guard 。您现在总共需要 (X+Y)*n 时间。这是一个常数因子，当 n 变得非常大时，与 n 因子相比，(X+Y) 因子变得可以忽略不计。也就是说，如果您可以将函数 X*n 简化为 (X+Y)*(log n)，那么就值得添加 Y code> 工作量，因为总共执行的迭代次数较少。

2. 同样的推理也适用于你的第二个问题。是的，检查“如果 X 或 Y”比检查“如果 X”需要更多时间，但它是一个常数因素。额外时间不随n的大小而变化。

在某些语言中，如果第一个条件失败，则仅检查第二个条件。我们如何解释这一点？最简单的解决方案是认识到比较次数的上限为 3，而 n 较大时迭代次数可能为数百万次。但 3 是一个常量，因此每次迭代最多会增加常量的工作量。您可以深入研究具体细节，并尝试推理第一个、第二个和第三个条件为真或为假的频率分布，但通常您并不真的想走这条路。假装你总是进行所有的比较。

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