前言

有需要的同学可以订阅专栏：Swift数据结构和算法专题
代码地址：Swift数据结构和算法代码

复杂度

这个项目以后会扩展吗？

这个古老的问题总是在软件开发的设计阶段被问到，并且有多种形式。从架构的角度来看，可扩展性是指更改应用程序的难易程度。从数据库的角度来看，可伸缩性是关于在数据库中保存或检索数据所需的时间。

对于算法，可扩展性是指算法在执行时间和内存使用方面随着输入大小的增加而执行的情况。

当我们处理少量数据时，低效率的算法可能仍然感觉很快。然而，随着数据量的增加，低效率的算法变得很糟糕。那么它会变得多糟糕呢？了解如何量化这是我们需要了解的一项重要技能。

在本章中，我们将了解 Big O 表示法在两个维度（执行时间和内存使用）中不同级别的可伸缩性。

时间复杂度

对于少量数据，由于现代硬件的速度，即使是最烂的算法也可能看起来很快。然而，随着数据的增加，低效率的算法的成本变得越来越明显。时间复杂度是随着输入大小的增加运行算法所需时间的度量。

恒定时间

恒定时间算法是一种无论输入大小如何都具有相同运行时间的算法。参考下面的代码：

func checkFirst(names: [String]) { 
  if let first = names.first { 
      print(first) 
  } else { 
      print("no names") 
  } 
}

names 数组的大小对该函数的运行时间没有影响。无论输入有 10 个项目还是 1000 万个项目，此函数都只检查数组的第一个元素。这是时间与数据大小之间的时间复杂度的可视化：

[图片上传失败...(image-45f300-1645529361634)]

随着输入数据的增加，算法所花费的时间不会改变。

为简洁起见，程序员使用一种称为 Big O 表示法的表示法来表示各种时间复杂度的大小。常数时间的大 O 表示法是 O(1)。

线性时间

我们看一下下面的代码：

func printNames(names: [String]) { 
    for _ in names { 
        for name in names { 
            print(name) 
        } 
    } 
}

这一次，该函数为数组中的每个名称打印出数组中的所有名称。如果您有一个包含十条数据的数组，它将十次打印十个名称的完整列表。那是 100 个打印语句。

如果将输入大小增加 1，它将打印 11 个名称的完整列表 11 次，产生 121 个打印语句。与之前以线性时间运行的函数不同，算法会随着数据量的增加而迅速失控。

下图说明了这种行为：

[图片上传失败...(image-f47ac1-1645529361634)]

随着输入数据大小的增加，算法运行所需的时间会急剧增加。因此，算法在规模上表现不佳。

二次时间的大 O 表示法是 O(n²)。

无论线性时间 O(n) 算法的编写效率如何（即便你加上各种等待算法），对于足够大的n，线性时间算法将比超级优化的二次算法执行得更快。

对数时间

到目前为止，我们已经了解了线性和二次时间复杂度，其中输入的每个元素至少检查一次。但是，在某些情况下，只需要检查输入的子集，从而加快运行时间。

属于这类时间复杂度的算法是可以通过对输入数据做出一些假设来利用一些捷径的算法。例如，如果我们有一个排序的整数数组，那么查找特定值是否存在的最快方法是什么？

一个天真的解决方案是从头到尾检查数组，在得出结论之前检查每个元素。由于我们要检查每个元素一次，这将是一个 O(n) 算法。线性时间相当不错，但你可以做得更好。由于输入数组已排序，因此您可以进行优化。考虑以下代码：

let numbers = [1, 3, 56, 66, 68, 80, 99, 105, 450]

func naiveContains(_ value: Int, in array: [Int]) -> Bool { 
    for element in array { 
        if element == value { 
            return true 
        } 
    }
    return false
}

如果我们要检查数组中是否存在数字 451，则朴素算法必须从头到尾迭代，对数组中的九个值进行总共九次检查。但是，由于数组已排序，因此可以可以立即通过检查中间值删除一半必要的比较：

func naiveContains(_ value: Int, in array: [Int]) -> Bool { 
    guard !array.isEmpty else { return false } 
    let middleIndex = array.count / 2

    if value <= array[middleIndex] { 
      for index in 0...middleIndex { 
        if array[index] == value { 
          return true 
        } 
      } 
    } else { 
      for index in middleIndex..<array.count { 
        if array[index] == value {
        return true
      }
    }
  } 
  return false
}

上面的函数做了一个小而有意义的优化，它只检查数组的一半来得出结论。

该算法首先检查中间值以查看它与所需值的比较情况。如果中间值大于期望值，则算法不会费心查看数组右半部分的值；由于数组已排序，中间值右侧的值只能变大。

在另一种情况下，如果中间值小于所需值，算法将不会查看数组的左侧。这是一个小而有意义的优化，它将比较次数减少了一半。

如果我们可以在整个方法中重复进行此优化会怎样？后面“二分查找”中会有更加详细的介绍。

可以重复丢弃一半所需比较的算法将具有对数时间复杂度。下图描述了对数时间算法在输入数据增加时的表现：

[图片上传失败...(image-74aba9-1645529361634)]

随着输入数据的增加，执行算法所需的时间以缓慢的速度增加。如果我们仔细观察，可能会注意到该图似乎表现出渐近行为。这可以通过考虑将需要进行的比较次数减半的影响来解释。

当我们的输入大小为 100 时，将比较减半意味着您可以节省 50 次比较。如果输入大小为 100,000，则将比较减半意味着您可以节省 50,000 次比较。你拥有的数据越多，减半效应的规模就越大。因此，可以看到图形似乎接近水平。

此类别中的算法很少，但在允许的情况下非常强大。对数时间复杂度的大 O 表示法是 O()。

是以 2 为底的对数、以 10 为底的对数还是自然对数？

在上面的例子中，log以2为底适用。然而，由于大 O 符号只关注性能的形状，实际的基数并不重要。

拟线性时间

我们会遇到的另一个常见时间复杂度是拟线性时间。拟线性时间算法的性能比线性时间差，但比二次时间好得多。它们是我们将要处理的最常见的算法之一。拟线性时间算法的一个例子是 Swift 的排序方法。

拟线性时间复杂度的 Big-O 表示法是 O(n log n)，它是线性时间和对数时间的乘积。因此，对数时间和线性时间之间的拟线性拟合；它比线性时间差，但仍比我们接下来将看到的许多其他复杂性好。这是图表：

[图片上传失败...(image-f01e1a-1645529361634)]

拟线性时间复杂度与二次时间具有相似的曲线，但上升速度没有那么快，因此对大型数据集更具弹性。

其他时间复杂度

到目前为止，我们遇到的五个时间复杂度就是上面遇到的那些。其他时间复杂度确实存在，但远不常见。这些时间复杂度包括多项式时间、指数时间、阶乘时间等。

需要注意的是，时间复杂度是对性能的高级概述，它并不能判断算法的速度超出一般的排序方案。这意味着两种算法可以具有相同的时间复杂度，但一种可能仍然比另一种快得多。对于小型数据集，时间复杂度可能不是实际速度的准确度量。

比较时间复杂度

假设我们编写了以下代码来查找从 1 到 n 的数字之和。

func sumFromOne(upto n: Int) -> Int { 
  var result = 0 for i in 1...n { 
    result += i 
  } 
  return result 
}
sumFromOne(upto: 10000)

代码循环 10000 次并返回 50005000。它是 O(n) 并且需要一点时间才能在操场上运行，因为它会计算循环并打印结果。

下面是另一个版本：

func sumFromOne(upto n: Int) -> Int { 
  (1...n).reduce(0, +) 
} 
sumFromOne(upto: 10000)

在 Playground 中，这将运行得更快，因为它从标准库中调用已编译的代码。但是，如果我们查看 reduce 的时间复杂度，您会发现它也是 O(n)，因为它调用了 n 次方法。它是同一个大 O，但具有更小的常量，因为它是编译代码。

最终我们写成下面这个样子：

func sumFromOne(upto n: Int) -> Int { 
  (n + 1) * n / 2 
} 
sumFromOne(upto: 10000)

这个版本的函数使用了 高斯在小学时注意到的一个技巧。也就是说，我们可以使用简单的算术计算总和。该算法的最终版本是 O(1) 并且很难被击败。始终首选恒定时间算法。如果你把这个版本放在一个循环中，你仍然会得到线性时间。之前的 O(n) 版本距离缓慢的二次时间只有一个外循环。

空间复杂度

算法的时间复杂度可以帮助预测可扩展性，但它不是唯一的指标。空间复杂度是算法运行所需资源的度量。对于计算机来说，算法的资源就是内存。我们看以下代码：

func printSorted(_ array: [Int]) { 
  let sorted = array.sorted() 
  for element in sorted { 
    print(element) 
  } 
}

上面的函数将创建数组的排序副本并打印数组。要计算空间复杂度，我们需要分析函数的内存分配。

由于array.sorted() 会产生一个与数组大小相同的全新数组，因此printSorted 的空间复杂度为O(n)。尽管此函数简单而优雅，但在某些情况下，我们可能希望分配尽可能少的内存。

我们可以将上述功能修改为以下内容：

func printSorted(_ array: [Int]) {

  // 1 
  guard !array.isEmpty else { return }

  // 2 
  var currentCount = 0 
  var minValue = Int.min

  // 3 
  for value in array { 
    if value == minValue { 
      print(value) 
      currentCount += 1 
    } 
  }

  while currentCount < array.count {

  // 4 
  var currentValue = array.max()!

  for value in array { 
    if value < currentValue && value > minValue { 
      currentValue = value 
    } 
  }

  // 5 
  for value in array { 
    if value == currentValue { 
      print(value) 
      currentCount += 1 
    } 
  }

  // 6 
  minValue = currentValue
  }
}

此实现尊重空间限制。总体目标是多次迭代数组，为每次迭代打印下一个最小值。这是这个算法正在做的事情：

1. 检查数组是否为空的情况。如果是，则没有可打印的内容。

2. currentCount 记录打印语句的数量。 minValue 存储最后打印的值。

3. 算法首先打印出所有匹配 minValue 的值，并根据打印语句的数量更新 currentCount。

4. 使用 while 循环，算法找到大于 minValue 的最小值并将其存储在 currentValue 中。

5. 然后算法在更新 currentCount 的同时打印数组中 currentValue 的所有值。

6. minValue 设置为 currentValue，因此下一次迭代将尝试找到下一个最小值。

上述算法只分配内存来跟踪少数变量，因此空间复杂度为 O(1)。这与前面的函数相反，它分配整个数组来创建源数组的排序表示。

其他标识

到目前为止，我们已经使用大 O 表示法评估了算法。这是迄今为止程序员评估时最常用的衡量标准。但是，也存在其他符号。

Big Omega 表示法用于衡量算法的最佳情况运行时间。这不如大 O 有用，因为获得最好的情况通常是站不住脚的。

Big Theta 表示法用于测量具有相同最佳和最坏情况的算法的运行时间。

Playground 基于行的执行错误

本书广泛使用Playground。在某些情况下，可能会发现 Xcode 13 错误地禁用了基于行的执行。在这些情况下，只需使用 Playground 窗口底部的执行控制按钮即可运行整个 Playground。

关键点

• 时间复杂度是随着输入大小的增加运行算法所需时间的度量。

• 我们应该了解常数时间、对数时间、线性时间、拟线性时间和二次时间，并能够按成本对它们进行排序。

• 空间复杂度是算法运行所需资源的度量。

• 大O 符号用于表示时间和空间复杂度的一般形式。

• 时间和空间复杂度是可扩展性的高级度量；它们不测量算法本身的实际速度。

• 对于小型数据集，时间复杂度通常无关紧要。例如，当 n 很小时，拟线性算法可能比二次算法慢。

上一章	目录	下一章