swift 数据结构与算法一

algorithms and data structures 系列笔记一

1. 线性搜索（Linear Search）

线性搜索的目的是在数组中找到特定的值。

一个存储有某个类型对象的数组，你迭代遍历它，使其每个对象和你要找到的对象进行对比，如果两个对象相同，停止查找并返回当前 index，如果不相同，继续迭代查找。

例如数组 [5, 2, 4, 7]，存有 numbers 对象，你想确定该数组是否包含数字 2 。

你拿第一个数字 5 与 2 相比，不相等，则继续查找。

下一个 2 和要查找的数字相同，查找成功，停止迭代，返回 index 1 ，index 1 代表数组中下标为第二个元素，第一个下标为 0。

示例代码：

func linearSearch<T: Equatable>(_ array: [T], _ object: T) -> Int? {
  for (index, obj) in array.enumerated() where obj == object {
    return index
  }
  return nil
}

在 playground 键入代码，效果如下：

let array = [5, 2, 4, 7]
linearSearch(array, 2)  // This will return 1

2. 线性搜索性能 Linear Search Performance

Linear search 时间复杂度为 O(n) 。它将需要查找的对象和数组中每个对象对比，因此它的时间取决于数组的长度。在最坏的情况，需要遍历数组中所有对象才能确定数组中是否包含要查找的对象。在最好的情况，你只要对比一次就能确定了，比如第一个就是要查找的对象。最好的时间复杂度是 O(1) ，但是这很罕见，在一个随机分配的数组中，这个概率是 1:n 。平均而言，线性搜索需要查看数组中一半的对象。

3. 时间复杂度 O 符号介绍

A note on Big-O notation

大 O 符号可以粗略地显示算法的运行时间和它所使用的内存空间。当有人说， “这个算法最坏情况运行时间的O(n ^ 2)，并使用O(n)空间” ，他们说这是有点缓慢但不需要很多额外的内存。

各个时间复杂度对比：

Big-O	算法数量级	描述
O(1)	常量	最好的算法。无论要测试的数据量多大，该算法总是返回相同的时间。例如，数组中根据其 index 查找某个对象 。
O(log n)	对数	较好的算法。如果测试数据为100，大概查询7次，如果数据量1000，大概查询10次。这种算法，要查找的数据量越大，表现效果越好。
O(n)	线性	性能优良。 测试数据量100，需要查询100次，测试数据量1ooo，需要查找1000次。例如，顺序查找。
O(n log n)	linearithmic	性能良好。表现差于 linear 算法，但是也不是太坏。
O(n^2)	二次方的	查找速度慢。如果你有100个对象，需要查询 100^2 = 10,000 次
O(n^3)	三次方的	查找速度更慢。如果你有100个对象，需要查询 100^3 = 1000,000 次
O(2^n)	指数	查找速度非常慢。应当尽量避免这种算法，但是有时又没得选择，例如 traveling salesperson problem
O(n!)	阶乘	无法忍受的慢。百万年做不了一件事的那种慢。

以下为各个算法的一个示例：

O(1)

let value = array[5]

O(1) 的另一一个例子就是入栈出栈。

O(log n)

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

O(n)

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

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^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^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)

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!)

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

参考：

1. Implementing Linear Search
2. Big-O Notation