Swift 算法基础+实践 01

原文链接: https://eternityi.github.io/2017/10/09/swift-algorithems-basic-01/

数据结构

• 数组 Array
• 堆栈、队列 Stack/Queue
• 优先队列（堆） Priority Queue(heap)
• 链表（单链表/双向链表）LinkedList(single/double)
• 树、二叉树 Tree/BinaryTree
• 二叉搜索树 Binary Search Tree
• 哈希表 HashTable
• 集合 Disjoint Set
• 前缀树 Trie Tree
• 布隆过滤器 BloomFilter
• LRU Cache

分析常见的数据结构，以及这些数据结构在Swift、Objective-C的使用。

更重要的是实际应用，关于应用每篇文章会从两个方面来进行研究：

• 涉及使用这些基本数据结构解决常见的一些问题
• iOS/macOS SDK中对这些数据结构的实现和优化

算法复杂度

Big O Notation

• O(1): Constant Complexity: 常数复杂度
• O(log n): Logarithmic Complexity: 对数复杂度
• O(n): Linear Complexity: 线性时间复杂度
• O(n^2): N square Complexity 平⽅
• O(n^3): N square Complexity ⽴⽅方
• O(2^n): Exponential Growth 指数
• O(n!): Factorial 阶乘

O(1) 常数复杂度

O(1)时间复杂度的算法执行的时间是固定时间，理论上，执行时间和算法的输入是无关的。
最常见的就是数组中元素的访问操作:

let arr = [1, 1, 3, 5, 8];
arr[2]; // => 3

类似的还有数组的 push() 和 pop() 操作

O(n) 线性复杂度

O(n)时间复杂度的算法，执行时间和算法接收的输入n的大小是相关的。
最常见的就是数组遍历：

for (var i = 0; i < array.length; i++) {
  print(array[i]);
}