重要链接

什么是算法和数据结构？－做薄饼！

为什么要学习算法？－还在担心这不是你的菜吗？请读一下这篇文章。

大 O 表示法－我们经常会听到这样的话：“这个算法是 O(n) 的”。如果你不知道这是啥意思，请读读这篇文章。

*算法设计技巧－怎样设计自己的算法？

什么是算法和数据结构？

一个算法就像一张教计算机“烹饪”的“食谱”。如果你了解做菜的过程，你就能理解算法的定义。

下面有一张关于制作薄饼的食谱：

1. 首先，将面粉、泡打粉、盐和白砂糖倒入一个大碗中。

2. 加入牛奶、鸡蛋和融化了的奶油。

3. 搅拌混合直至丝柔顺滑。

4. 中火加热平底锅。

5. 将搅拌好的面糊缓慢倒入锅中，每个薄饼大概用 1/4 CUP 的面糊即可。

6. 薄饼两面都呈黄褐色即可出锅享用了。

这张食谱由一系列的步骤组成，你只需一步接一步按照指令来就可以了。算法也是如此，只不过它的指令是交给计算机去执行的，而不是厨师。

这些原料(面粉、牛奶、鸡蛋、黄油等)相当于算法中的待处理数据。这些原始数据(各种不同的原料)作为算法的输入，输出的数据(好吃的薄饼)即是结果。

那数据结构是什么呢？数据结构用于持有算法需要处理的数据。例如在薄饼食谱中，数据结构对应于用来装面粉的袋子、用于搅拌原料的碗、用于烹饪的平底锅以及最终用于盛烤好的薄饼的盘子。

为什么要学习算法与数据结构？

如果你已经写过一些代码，你也许就会好奇学习算法和数据结构的意义何在，特别是如果你没有接受过计算机科学专业的高等教育。

毕竟，在平时的编码工作中，到底会有多少机会需要自己亲自编写一个链表或排序算法呢？答案是：可能永远都不会。

然而...

了解一点现有算法解决问题时所用的奇技淫巧可能会给予你启发，让你能更好地优化自己的代码。

除了自带的标准数组和字典之外，了解一些其它的数据结构让你在构建自己的 App 时拥有更多的选择。

学习算法和数据结构会助你成为更好的开发者！（当然也就意味了可以赚到更多的 ¥¥¥。）

运用算法能让你编写出其它方式编写不出的软件

过去曾经在编写 App 时遇到过瓶颈，无法继续编写下去，因为我陷入到了一些基础的问题中，无法自拔。

通常的瓶颈都是运行速度的问题，我的 App 不够快。现在回想起来，原因多是我在解决问题是选用了错误的算法。如果我当时知道 O(n) 和 O(n^2) 之间的区别，或许就能克服这些瓶颈了。

对于小规模的数据量简单粗暴的方法往往能很好的完成工作，但事情并不总是如人所愿。对于大数据量，你需要使用更加聪明的算法。

还有些时候，我对自己所面对的问题根本就手足无措，甚至写不出来一个运行较慢的正确算法，不知道从何处下手。这时候，如果了解一些算法理论，就会有更多的方法可供尝试。

不要死记硬背算法实现

本文的目的不在于此。你应该试着去理解不同的算法是如何解决不同的问题的，而不是死记硬背。

学习一些算法技术，例如：分而治之、动态规划、贪婪算法等，可以助你更好地理解算法之间的快慢差异，并学会在算法对时间和空间的使用上做出平衡。

所以本文的主要目的是教会你如何更好的跟计算机打交道。

放轻松，算法并没有听起来那么可怕

很多算法书开篇就摆上来很多数学理论，数学公式固然有用，但初学并不需要。所以不要被那些公式吓到了。只要写过代码，你就能很好地理解那些神奇的算法和数据结构背后的原理。

相信我，算法是很有趣的。:-)

大O表示法

知道某个算法的运行速度和占用的内存空间，对于选择正确的算法来解决问题非常有帮助。

大O表示法 能让你对一个算法的运行时间和占用内存有个大概概念。当有人说，“这个算法在最糟情况下的运行时间是 O(n^2)，而且占用了 O(n) 大小的空间”时，他的意思是这个算法有点慢，不过没占多大内存。

要知道一个算法的大O 表示法通常要通过数学分析。在这里我们不会涉及具体的数学，不过知道不同的值意味着什么会很有用。所以这里有一张方便的表。n 在这里代表的意思是数据的个数。举个例子，当对一个有 100 个元素的数组进行排序时，n = 100。

以下是每种大O表示法的示例：

O(1)

O(1)复杂性的最常见示例是访问数组索引。

let value = array[5]

另外一个O(1)的例子是栈的推进和弹出。

O(log n)

var j = 1
while j < n {
  // do constant time stuff
  j *= 2
}

不是简单地递增，'j'在每次运行中增加2倍。二分搜索算法是O(log n)复杂度的示例。

O(n)

for i in stride(from: 0, to: n, by: 1) {
  print(array[i])
}

数组遍历和线性搜索是O(n)复杂性的示例。

O(n log n)

for i in stride(from: 0, to: n, by: 1) {
var j = 1
  while j < n {
    j *= 2
    // do constant time stuff
  }
}

或

for i in stride(from: 0, to: n, by: 1) {
  func index(after i: Int) -> Int? { // multiplies `i` by 2 until `i` >= `n`
    return i < n ? i * 2 : nil
  }
  for j in sequence(first: 1, next: index(after:)) {
    // do constant time stuff
  }
}

合并排序和堆排序是O(n log n)复杂度的示例。

O(n^2)

for i  in stride(from: 0, to: n, by: 1) {
  for j in stride(from: 1, to: n, by: 1) {
    // do constant time stuff
  }
}

遍历简单的二维数组和冒泡排序是O(n^2)复杂度的示例。

O(n^3)

for i in stride(from: 0, to: n, by: 1) {
  for j in stride(from: 1, to: n, by: 1) {
    for k in stride(from: 1, to: n, by: 1) {
      // do constant time stuff
    }
  }
}

O(2^n)

具有运行时间O(2^N)的算法通常是递归算法，其通过递归地解决大小为N-1的两个较小问题来解决大小为N的问题。
以下示例打印了解决著名的N盘“汉诺塔”问题所需的所有动作。

func solveHanoi(n: Int, from: String, to: String, spare: String) {
  guard n >= 1 else { return }
  if n > 1 {
    solveHanoi(n: n - 1, from: from, to: spare, spare: to)
  } else {
    solveHanoi(n: n - 1, from: spare, to: to, spare: from)
  }
}

O(n!)

下面给出了O(n!)的最简单的例子。

func nFactFunc(n: Int) {
  for i in stride(from: 0, to: n, by: 1) {
    nFactFunc(n: n - 1)
  }
}

大部分情况下你用直觉就可以知道一个算法的大O 表示法，不需要使用数学。比如说，如果你的代码用一个循环遍历你输入的每个元素，那么这个算法就是 O(n)。如果是循环嵌套循环，那就是 O(n²⁾。如果3个循环嵌套在一起就是 O(n3)，以此类推。

注意，大O 表示法只是一种估算，当数据量大的时候才有用。举个例子，插入排序的最糟情况运行时间是 O(n^2)。 理论上来说它的运行时间比归并排序要慢一些，归并排序是 O(n log n)。但对于小数据量，插入排序实际上更快一些，特别是那些已经有一部分数据是排序好的数组。

如果你看完没懂，也不要太纠结了。这种东西仅仅在比较两种算法哪种更好的时候才有点用。但归根结底，你还是要实际测试之后才能得出结论。而且如果数据量相对较小，哪怕算法比较慢，在实际使用也不会造成太大的问题。

算法设计技巧

当你遇到新问题的时候，需要寻找新的算法。

是否有类似的其它问题？

如果您可以根据另一个更普遍的问题来构建解决你目前需要解决问题，那么您可以使用现有算法。 为什么重新发明轮子？

我喜欢Steven Skiena的算法设计手册，它包含了一系列可以尝试的问题和解决方案。(另见Steven Skiena的算法库)

译注：豆瓣 算法设计手册

可以从暴力方案开始

原始而暴力的解决方案通常对实际使用而言太慢，但它们是一个很好的起点。 通过编写暴力解决方案，您将学习如何理解问题的真正含义。

一旦你有一个暴力实施方案，就可以使用它来验证你提出的任何改进是否正确的。

如果您只使用小型数据集，那么暴力方法实际上可能足够好。 不要陷入过早优化的陷阱！

分而治之

“当你改变你看待事物的方式时，你看到的东西会发生变化。”
—— 马克斯·普朗克，量子物理学家和诺贝尔奖获得者

分而治之是一种处理大问题的方法，将其分解成碎片并逐步向解决方案迈进。

不是将整个问题看作一个单一，庞大而复杂的任务，而是将问题分成相对较小的问题，这样问题更容易理解和处理。

您可以解决较小的问题并聚合解决方案，直到您只使用解决方案。 在每个步骤中，手头的问题都会缩小，解决方案会变得成熟，直到您拥有最终正确的解决方案。
将问题分解为规模更小的子问题，将这些规模更小的子问题逐个击破，然后将已解决的子问题合并，最终得出“母”问题的解。

将相同的解决方案重复地（或经常递归地）应用于解决较小的任务，从而在更短的时间内获得结果。