1. 斐波那契数列

斐波那契数列（Fibonacci Sequence），又称黄金分割数列。因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”

斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、55...。它从第三项开始，每一项都等于前两项之和。而实现这个数列的算法有很多种，每种算法都有各自的特点。我们可以通过实现一个斐波那契数列，对各种算法之间的特点进一步分析

1.1 递归算法

  1. class FibonacciSequence {
  3.     // 递归法
  4.     func f(n : Int) -> Int {
  5.         if(n < 3) { return 1; }
  6.         return f(n: n - 2) + f(n: n - 1);
  7.     }
  8. }

我们使用最简单的方式考量算法的性能，通过算法的执行代码行数评估

假设：n = 3，算法需要经过两次递归，分别执行2行代码。两次递归调用分别进行return，又执行了2行代码。所以当n = 3时共执行4行代码

当n为任意数字时，我们则需要将递归展开，才能完整的统计出执行代码的行数

假设：n = 5，依次递归的结果为1、1、2、3、5。将递归方法依次展开后，它会以二叉树的形态展示
image.png

结点f(5)下，有4个非终端结点和5个叶子结点。通过二叉树我们发现，叶子结点的数量，和左侧斐波那契数列的计算结果是一致的

在二叉树中，所有的叶子结点，代表的都是return 1的那一句代码。也就是说，所有的叶子结点执行代码的行数，等于斐波那契数列的计算结果，也就是f(n)的结果

而二叉树的另一个特性，非终端结点 = 叶子结点 - 1。依据这个特性，非终端结点执行代码的行数，应该等于f(n) - 1。但是，非叶子结点代表的是f(n: n - 2) + f(n: n - 1)这行代码，由于代码中使用了两次方法递归，所以正确的公式应该为(f(n) - 1) * 2，即：2(n) - 2

递归算法的执行代码行数，公式应为：f(n) + 2f(n) - 2，即：3f(n) - 2

按照示例中n = 5代入公式进行计算，f(n)的执行结果为5，即：3 * 5 - 2 = 13

所以当n = 5时，递归算法需要执行13行代码才可以计算出结果。同理，当n = 45时，f(n) = 1134903170，执行代码的行数为：3 * 1134903170 - 2 = 3404709508

由此可见，通过递归算法实现的斐波那契数列，执行效率非常差。原因在于它会重复计算一些已知的结果，我们可以通过其他算法对其进行优化

1.2 动态规划法

动态规划（Dynamic programming，简称DP），通过把原问题分解为相对简单的⼦问题的⽅式求解复杂问题的⽅法

动态规划法的三个核心要素：

  • 找到最优子结构（可以将问题拆解，找到最优的拆解方式）

  • 找到算法的边界（结束条件）

  • 状态转移方程式

代码实现：

  1. class FibonacciSequence {
  3.     // 动态规划法
  4.     func f(n : Int) -> Int {
  6.         var arr = [Int].init(repeating: 1, count: n + 1);
  8.         for i in 3 ... n {
  9.             arr[i] = arr[i - 1] + arr[i - 2];
  10.         }
  12.         return arr[n];
  13.     }
  14. }
  • 动态规划法返回结果需要执行的代码行数，初始化的代码行数 + for循环的执行次数 + 循环内部代码的执行次数 + 返回结果的代码行数 = 1 + (n - 1) + (n - 2) + 1 = 2n - 1。当n = 45时，执行代码的行数为：89

上述代码中，我们使用额外空间记录了每一次的执行结果，属于空间换取时间的一种做法

一个算法所使用的空间复杂度，它和时间复杂度同样重要。例如：⼀个程序花费了很多时间，但是它仍然处于运⾏中，只是需要等待更⻓的时间。但是⼀个程序占⽤⼤量内存，它可能根本⽆法运⾏。此时，我们只能降低算法的空间复杂度

上述代码中，我们每次计算只需要n - 1和n -2这两步的结果，并不需要每一次的结果都存储。所以，我们可以对算法的空间进一步优化：

  1. class FibonacciSequence {
  3.     // 动态规划法 - 空间优化
  4.     func f(n : Int) -> Int {
  6.         var n1 = 1;
  7.         var n2 = 1;
  9.         for _ in 3 ... n {
  10.             let sum = n1 + n2;
  11.             n1 = n2;
  12.             n2 = sum;
  13.         }
  15.         return n2;
  16.     }
  17. }
  • 优化后的代码，只使用一个临时变量作为额外空间，它进一步优化了空间复杂度。但它使得循环内部的代码量变多，这会导致代码的执行次数增长至4n

我们评估这两种算法的优劣，需要有更确切的⽅式描述我们对算法分析的结构。即：大O表示法

大O表示法的意义，允许我们对算法⾏为的所有细节不那么在意。例如：算法3虽然⽐算法2慢⼀些，但是实际开发中算法2分配数组也需要⼀部份时间。这意味着在实际时间中，两种算法彼此更接近。但是对于算法3和算法1，会很明显得出4n⽐3f(n) - 2要好得多

所以，对于算法2和算法3来说，使用大O表示法，它们的时间复杂度都是O(n)

1.3 矩阵乘法

f(n)依赖于f(n - 1)和f(n - 2)，将其依赖的状态存成列向量：
image.png

目标值f(n)所在矩阵为：
image.png

根据矩阵乘法，不难发现：
image.png

令：
image.png

根据递推式得：
image.png

再根据矩阵乘法具有【结合律】，最终可得：
image.png

代码实现：

  1. class FibonacciSequence {
  3.     // 矩阵乘法
  4.     func f(n : Int) -> Int {
  6.         if(n < 3) {
  7.             return 1;
  8.         }
  10.         let c = n - 1;
  12.         var def = [[Int]].init(repeating: [Int].init(repeating: 1, count: 2), count: 2);
  13.         def[1][1] = 0;
  14.         var res = def;
  16.         for _ in 1 ..< c {
  17.             res = matrixMultiply(mat1: def, mat2: res);
  18.         }
  20.         return res[0][0];
  21.     }
  23.     fileprivate func matrixMultiply(mat1 : [[Int]], mat2 : [[Int]]) -> [[Int]] {
  25.         var res = [[Int]].init(repeating: [Int].init(repeating: 0, count: 2), count: 2);
  27.         for i in 0 ..< 2 {
  28.             for j in 0 ..< 2 {
  29.                 res[i][j] = mat1[i][0] * mat2[0][j] + mat1[i][1] * mat2[1][j];
  30.             }
  31.         }
  33.         return res;
  34.     }
  35. }

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)

由此可见，使用矩阵乘法，和动态规划法的区别并不大。我们针对时间复杂度，还可以进一步优化

1.4 矩阵快速幂

矩阵乘法在计算mat的n - 1次方时，如果直接求取，时间复杂度是O(n)。我们可以套用快速幂算法，加速这里的mat ^ (n - 1)的求解

快速幂：顾名思义，就是快速算底数的n次幂。其时间复杂度为O(log₂n)，它与朴素的O(N)相比效率有了极大的提高

核心思想：就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变

例如：

  1. 3 ^ 10 = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 = 59049
  2. 3 ^ 10 = (3 ^ 5) ^ 2 = 243 ^ 2 = 59049
  3. 3 ^ 5 = (3 ^ 4) * 3 = (81 * 3) = 243
  4. 3 ^ 4 = (3 ^ 2) ^ 2 = 9 ^ 2 = 81
  5. 3 ^ 2 = (3 ^ 1) ^ 2 = 9

  • x ^ n，通过n计算m，即：m = n / 2

    • 如果n为偶数，x ^ n = (x ^ m) ^ 2

    • 如果n为奇数，x ^ n = ((x ^ m) ^ 2) * x

代码实现：

  1. class FibonacciSequence {
  3.     // 矩阵快速幂
  4.     func f(n : Int) -> Int {
  6.         var def = [[Int]].init(repeating: [Int].init(repeating: 1, count: 2), count: 2);
  7.         def[1][1] = 0;
  8.         var res = def;
  10.         var odd = "";
  11.         var n = n - 1;
  13.         while(n > 1){
  14.             odd = "\(n & 1)" + odd;
  15.             n = n / 2;
  16.         }
  18.         for c in odd {
  20.             res = matrixMultiply(mat1: res, mat2: res);
  22.             if(Int("\(c)") == 1){
  23.                 res = matrixMultiply(mat1: res, mat2: def);
  24.             }
  25.         }
  27.         return res[0][0];
  28.     }
  30.     fileprivate func matrixMultiply(mat1 : [[Int]], mat2 : [[Int]]) -> [[Int]] {
  32.         var res = [[Int]].init(repeating: [Int].init(repeating: 0, count: 2), count: 2);
  34.         for i in 0 ..< 2 {
  35.             for j in 0 ..< 2 {
  36.                 res[i][j] = mat1[i][0] * mat2[0][j] + mat1[i][1] * mat2[1][j];
  37.             }
  38.         }
  40.         return res;
  41.     }
  42. }
  • 使用快速幂算法来加速x ^ n的求解，时间复杂度可优化为O(log n)

1.5 通项公式

根据斐波那契数列的通项公式：
image.png

可以实现以下方法：

  1. class FibonacciSequence {
  3.     // 通项公式
  4.     func f(n : Int) -> Int {
  5.         let sqrt5 = sqrt(5);
  6.         let res = pow((1 + sqrt5) / 2, Double(n)) - pow((1 - sqrt5) / 2, Double(n));
  7.         return Int(res / sqrt5);
  8.     }
  9. }
  • 这种方式将时间复杂度优化至O(1)。但算法中使用了sqrt和pow等数学函数，它们的计算也需要时间，所以它并不一定是最优算法

2. LRU算法

LRU（最近最少使⽤），是⼀种缓存淘汰算法。顾名思义，最⻓时间没有被使⽤的元素会被从缓存中淘汰

  • 缓存有大小限制

  • 一定是按照某种特定顺序存储数据，例如：最近最少使用的

  • 可以使用数组进行顺序存储，或者使用链表进行链式存储

  • HashMap是典型的key-value存储结构，配合使用可将缓存的查找优化为O(1)

  • 缓存命中后要移动数据

2.1 方案分析

例如，我们有⼀个容量为3的缓存：
image.png

  • 先后插入数据8、9、6，此时缓存已满。如果再插入数据3，需要遵循LRU的规则，先将最⻓时间没有被使⽤的数据8删除，然后插入数据3

通过案例分析，我们发现LRU缓存的规则和队列（Queue）的数据结构很相似，它符合队列的先进先出原则。由于缓存的⼤⼩是有限的，该队列具有特定容量。当引⼊⼀个新元素时，它就会被添加到队列的尾部。而需要淘汰的元素，将被放在队列的头部

但使用队列也存在一些缺陷。由于每⼀项存储的是key-value形式，通过key取value时，需要遍历，它的时间复杂度和空间复杂度都为O(n)

2.2 方案优化

如果想将时间复杂度降低到O(1)，仅使用队列是无法实现的

我们可以通过双向链表与Hash表结合使用：
image.png

  • Hash表⽤来存储key-value，将缓存的查找优化到O(1)

  • 双向链表⽤来管理缓存顺序。双向链表具备头指针和尾指针，结点的数据结构中保存了前驱和后继，所以通过双向链表找到链表的头、尾，对结点进行插入、删除与移动，时间复杂度同样优化到O(1)

2.3 方案选择

使用双向链表与Hash表的方案，同样有它的缺陷。双向链表中的头结点与尾结点，以及每一个结点中的前驱和后继，都需要额外的存储空间，使内存的消耗大大提升

如果我们只需要一个⼩数据量的LRU，即使通过遍历查找，也不会过多的影响执行效率。此时可以考虑数组的使用，这样的方案代码实现简单，而且不会增加额外的空间成本

链表与数组的对比：
image.png

  • 链表特点：查找麻烦，插⼊和删除容易

  • 数组特点：查找容易，插⼊和删除困难

由此可见，每一种方案都会存在它的优势与劣势。所以我们要根据具体需求，从而选择出更适合的方案

2.4 数组方案

数组方案属于顺序存储，可以通过索引直接访问，不需要额外存储指针域，所以这个方案占用的内存更小。由于缓存查找需要遍历，而移动和删除操作困难，所以这个方案实现的缓存，容量不宜过大

2.4.1 缓存协议

创建LRUCacheProtocol.swift类，定义LRU缓存协议：

  1. protocol LRUCacheProtocol {
  2.     func getCacheValue() -> String;
  3. }

2.4.2 数据结构

创建LRULinear.swift类，定义缓存和结点对象的数据结构：

  1. class LRULinear<Element: LRUCacheProtocol & Comparable> {
  3.     fileprivate class Entry {
  5.         var key : Element;
  6.         var value : String;
  8.         init(k : Element, v : String){
  9.             key = k;
  10.             value = v;
  11.         }
  12.     }
  14.     // 总容量
  15.     fileprivate var _numItems : Int;
  16.     // 缓存数组
  17.     fileprivate var _cache : [Entry]?;
  18. }

2.4.3 初始化 & 打印

实现缓存的初始化与打印方法：

  1. class LRULinear<Element: LRUCacheProtocol & Comparable> {
  3.     // 初始化
  4.     init(capacity : Int){
  5.         _numItems = capacity;
  6.         _cache = [Entry]();
  7.     }
  9.     // 打印
  10.     func traverse() -> String {
  12.         var str = "";
  14.         for entry in _cache! {
  15.             str += "key：\(entry.key)，value：\(entry.value)\n";
  16.         }
  18.         return str;
  19.     }
  20. }

2.4.4 插入 & 读取

实现缓存的插入与读取：

  1.     func objectForKey(key : Element) -> String {
  3.         // 1、遍历缓存
  4.         for i in 0 ..< _cache!.count {
  6.             // 获取当前缓存对象
  7.             let entry = _cache![i];
  9.             // 不匹配，跳过
  10.             if(entry.key != key){
  11.                 continue;
  12.             }
  14.             // 2、匹配，更新缓存
  15.             entry.value = key.getCacheValue();
  17.             // 如果访问的缓存在队尾，说明是最新被使用的
  18.             if(i == _numItems - 1){
  19.                 // 直接将缓存的值返回
  20.                 return entry.value;
  21.             }
  23.             // 否则，将该缓存从数组中删除
  24.             _cache?.remove(at: i);
  25.             // 然后将其重新添加至队尾，将其更新为最新使用
  26.             _cache?.append(entry);
  28.             // 最后将缓存的值返回
  29.             return entry.value;
  30.         }
  32.         // 3、未能找到缓存，查看数组容量如果已满，删除头部数据，因为它是最⻓时间没有被使⽤的
  33.         if(_cache!.count == _numItems){
  34.             _cache?.remove(at: 0);
  35.         }
  37.         // 创建一个新的缓存对象
  38.         let entry = Entry.init(k: key, v: key.getCacheValue());
  39.         // 将其添加至队尾
  40.         _cache?.append(entry);
  42.         // 将缓存的值返回
  43.         return entry.value;
  44.         }
  46.         // 3、未能找到缓存，查看数组容量如果已满，删除头部数据，因为它是最⻓时间没有被使⽤的
  47.         if(_cache!.count == _numItems){
  48.             _cache?.remove(at: 0);
  49.         }
  51.         // 创建一个新的缓存对象
  52.         let entry = Entry.init(k: key, v: key.getCacheValue());
  53.         // 将其添加至队尾
  54.         _cache?.append(entry);
  56.         // 将缓存的值返回
  57.         return entry.value;
  58.     }

2.4.5 代码测试

创建String+LRUCache.swift类，让String遵循LRU缓存协议：

  1. extension String : LRUCacheProtocol {
  3.     func getCacheValue() -> String{
  4.         return "CacheValue-\(self)";
  5.     }
  6. }

添加缓存并打印结果：

  1. let cache = LRULinear<String>(capacity: 5);
  3. cache.objectForKey(key: "1");
  4. cache.objectForKey(key: "2");
  5. cache.objectForKey(key: "3");
  6. cache.objectForKey(key: "4");
  7. cache.objectForKey(key: "5");
  8. cache.objectForKey(key: "6");
  9. cache.objectForKey(key: "1");
  11. print("\(cache.traverse())");
  13. -------------------------
  14. //输出以下内容：
  15. key：3，value：CacheValue-3
  16. key：4，value：CacheValue-4
  17. key：5，value：CacheValue-5
  18. key：6，value：CacheValue-6
  19. key：1，value：CacheValue-1

2.5 链表 + Hash表

链表方案属于链式存储，可以很容易完成插⼊和删除操作，但是查找麻烦。使用Hash表配合，可以弥补查找的缺陷

2.5.1 链表介绍

链表是动态的线性数据结构，不可以随机访问数据，需要从头遍历。链表中的元素通常不存储在连续的位置。所以链表中的结点通常由数据 + 指针组成。所以该方案的执行效率最高，适合缓存容量较大时使用

链表种类：

  • 单链表：结点 = 数据 + 指针。指针指向下⼀个结点。单链表中的第⼀个结点和最后⼀个结点，分别叫做头结点和尾结点，只能从前往后遍历。尾结点是⼀个特殊的结点，它的指针总是指向NULL，代表结尾。头结点分为两种：

    • 有虚拟头结点，开发中经常使用，它的好处在于统⼀结点的操作⽅式，代码实现更⽅便

    • ⽆虚拟头结点，在面临操作头尾结点时，需要增加额外判断，并进行特殊处理，使用相对麻烦

  • 双向链表：结点 = 前指针 + 数据 + 后指针，前指针和后指针分别指向当前结点的前趋结点和后继结点，允许我们从两个⽅向进⾏操作。头结点和尾结点都是虚拟结点

  • 循环链表：跟单链表相⽐，尾结点不在指向NULL，⽽是指向头结点

对链表的操作有：

  • Insert插⼊结点

  • Delete删除结点

  • Search搜索结点

2.5.2 数据结构

创建LRULinked.swift类，定义缓存和结点对象的数据结构：

  1. class LRULinked<Element: LRUCacheProtocol & Comparable & Hashable> {
  3.     fileprivate class Node {
  5.         var key : Element?;
  6.         var value : String?;
  7.         // 前驱结点
  8.         var prev : Node?;
  9.         // 后继结点
  10.         var next : Node?;
  12.         init(){}
  14.         init(k : Element, v : String){
  15.             key = k;
  16.             value = v;
  17.         }
  18.     }
  20.     // 总容量
  21.     fileprivate var _numItems : Int;
  22.     // 当前长度
  23.     fileprivate var _length : Int;
  24.     // 虚拟头结点
  25.     fileprivate var _head : Node?;
  26.     // 虚拟尾结点
  27.     fileprivate var _tail : Node?;
  28.     // Hash表
  29.     fileprivate var _hash : [Element: Node]?;
  30. }
  • 为了操作方便，使用虚拟头结点和虚拟尾结点

2.5.3 初始化 & 打印

实现缓存的初始化与打印方法：

  1. class LRULinked<Element: LRUCacheProtocol & Comparable & Hashable> {
  3.     // 初始化
  4.     init(capacity : Int){
  6.         _numItems = capacity;
  7.         _length = 0;
  9.         _head = Node();
  10.         _tail = Node();
  11.         _hash = [Element: Node]();
  13.         // 头、尾结点默认连接在一起
  14.         _head?.next = _tail;
  15.         _tail?.prev = _head;
  16.     }
  18.     // 打印
  19.     func traverse() -> String {
  21.         var str = "";
  22.         var node = _head?.next;
  24.         // 从首元结点开始，遍历到尾结点结束，依次打印
  25.         while(node?.key != nil) {
  26.             str += "key：\(node!.key!)，value：\(node!.value!)\n";
  27.             node = node?.next;
  28.         }
  30.         return str;
  31.     }
  32. }

2.5.4 插入 & 读取

使用头插法，将结点插入链表头部，同时插入到Hash表中：

  1. class LRULinked<Element: LRUCacheProtocol & Comparable & Hashable> {
  3.     // 使用头插法，将结点插入链表头部，同时插入到Hash表中
  4.     fileprivate func addNodeToHead(node : Node) {
  6.         //将新结点插入到头结点和头结点的后继结点的中间
  8.         // 当前结点的后继，指向头结点的后继结点
  9.         node.next = _head?.next;
  10.         // 头结点的后继结点的前驱，指向当前结点
  11.         _head?.next?.prev = node;
  13.         // 当前结点的前驱，指向头结点
  14.         node.prev = _head;
  15.         // 头结点的后继，指向当前结点
  16.         _head?.next = node;
  18.         // 将缓存插入到Hash表
  19.         _hash![node.key!] = node;
  20.         // 缓存的当前长度+1
  21.         _length += 1;
  22.     }
  23. }

删除链表中最长不时间被使用的缓存：

  1. class LRULinked<Element: LRUCacheProtocol & Comparable & Hashable> {
  3.     // 从链表和Hash表中删除结点
  4.     fileprivate func removeNode(node : Node) {
  6.         // 将当前结点的前驱和后继相连，从而使它们和当前结点断开连接，相当于结点的删除
  7.         node.prev?.next = node.next;
  8.         node.next?.prev = node.prev;
  10.         // 将结点从Hash表中删除
  11.         _hash!.removeValue(forKey: node.key!);
  12.         // 缓存的当前长度-1
  13.         _length -= 1;
  14.     }
  16.     // 删除链表中最长不时间被使用的缓存
  17.     fileprivate func removeTailNode() -> Node {
  19.         // 获取尾结点
  20.         let lastNode = _tail!.prev!;
  21.         // 删除尾结点
  22.         removeNode(node: lastNode);
  24.         return lastNode;
  25.     }
  26. }

将缓存移动到链表头部：

  1. class LRULinked<Element: LRUCacheProtocol & Comparable & Hashable> {
  3.     // 将缓存移动到链表头部，表示该缓存是最长时间被使用的
  4.     fileprivate func moveNodeToHead(node : Node) {
  6.         // 得到首元结点
  7.         let firstNode = _head!.next!;
  9.         // 如果当前结点就是首元结点，说明已经是最长时间被使用的
  10.         if(node.key == firstNode.key){
  11.             // 什么都不做，直接返回
  12.             return;
  13.         }
  15.         // 否则，先删除当前结点
  16.         removeNode(node: node);
  17.         // 然后将当前结点插入到链表头部
  18.         addNodeToHead(node: node);
  19.     }
  20. }

实现缓存的插入与读取：

  1. class LRULinked<Element: LRUCacheProtocol & Comparable & Hashable> {
  3.     // 插入 & 读取
  4.     func objectForKey(key : Element) -> String {
  6.         // 1、从Hash表中，通过key获取结点
  7.         var node = _hash![key];
  9.         // 判断结点是否已存在
  10.         if(node != nil) {
  12.             // 2、已存在，更新缓存
  13.             node?.value = key.getCacheValue();
  14.             // 移动结点到链表头部
  15.             moveNodeToHead(node: node!);
  17.             // 最后将缓存的值返回
  18.             return node!.value!;
  19.         }
  21.         // 3、不存在，将缓存插入到链表和Hash表
  23.         // 判断容量是否已满
  24.         if(_length == _numItems){
  25.             // 容量已满，删除链表中最长不时间被使用的缓存
  26.             removeTailNode();
  27.         }
  29.         // 创建新结点
  30.         node = Node(k: key, v: key.getCacheValue());
  31.         // 将结点插入链表头部，同时插入到Hash表中
  32.         addNodeToHead(node: node!);
  34.         // 将缓存的值返回
  35.         return node!.value!;
  36.     }
  37. }

2.4.5 代码测试

添加缓存并打印结果：

  1. let cache = LRULinked<String>(capacity: 5);
  3. cache.objectForKey(key: "1");
  4. cache.objectForKey(key: "2");
  5. cache.objectForKey(key: "3");
  6. cache.objectForKey(key: "4");
  7. cache.objectForKey(key: "5");
  8. cache.objectForKey(key: "6");
  9. cache.objectForKey(key: "1");
  11. print("\(cache.traverse())");
  13. -------------------------
  14. //输出以下内容：
  15. key：1，value：CacheValue-1
  16. key：6，value：CacheValue-6
  17. key：5，value：CacheValue-5
  18. key：4，value：CacheValue-4
  19. key：3，value：CacheValue-3

总结

斐波那契数列：

  • 递归算法：执行效率非常差，原因在于它会重复计算一些已知的结果。时间复杂度：O(n ^ n)

  • 动态规划法：通过把原问题分解为相对简单的⼦问题的⽅式求解复杂问题的⽅法。时间复杂度：O(n)

  • 矩阵乘法：通过公式得知，利用1110的矩阵进行n - 1相乘进行求解。时间复杂度：O(n)

  • 矩阵快速幂：每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。时间复杂度：O(log₂n)

  • 通项公式：通过通项公式直接求解，算法中使用了sqrt和pow等数学函数，所以它并不一定是最优算法。时间复杂度：O(1)

LRU算法：

  • LRU（最近最少使⽤），是⼀种缓存淘汰算法。顾名思义，最⻓时间没有被使⽤的元素会被从缓存中淘汰

    • 缓存有大小限制

    • 存储数据一定是按照最近最少使用的顺序

    • 可以使用数组进行顺序存储，或者使用链表进行链式存储

    • HashMap是典型的key-value存储结构，配合使用可将缓存的查找优化为O(1)

    • 缓存命中后要移动数据

  • 方案分析：LRU缓存的规则和队列（Queue）的数据结构很相似，它符合队列的先进先出原则。由于缓存的⼤⼩是有限的，该队列具有特定容量。当引⼊⼀个新元素时，它就会被添加到队列的尾部。而需要淘汰的元素，将被放在队列的头部。但使用队列也存在一些缺陷。由于每⼀项存储的是key-value形式，通过key取value时，需要遍历，它的时间复杂度和空间复杂度都为O(n)

  • 方案优化：通过双向链表与Hash表结合使用。Hash表⽤来存储key-value，将缓存的查找优化到O(1)。双向链表⽤来管理缓存顺序。双向链表具备头指针和尾指针，结点的数据结构中保存了前驱和后继，所以通过双向链表找到链表的头、尾，对结点进行插入、删除与移动，时间复杂度同样优化到O(1)。由于头结点和尾结点、前驱和后继结点都需要额外的存储空间，使内存的消耗大大提升

  • 方案选择：每一种方案都会存在它的优势与劣势。所以我们要根据具体需求，从而选择出更适合的方案

    • 数组方案：数组方案属于顺序存储，可以通过索引直接访问，不需要额外存储指针域，所以这个方案占用的内存更小。由于缓存查找需要遍历，而移动和删除操作困难，所以这个方案实现的缓存，容量不宜过大

    • 链表+Hash表：链表方案属于链式存储，可以很容易完成插⼊和删除操作，但是查找麻烦。使用Hash表配合，可以弥补查找的缺陷。所以该方案的执行效率最高，适合缓存容量较大时使用