铁汁：哇，厉害厉害厉害，你胖你说都对，但还是没必要学啊。

小希：???

铁汁：现在很多网站啊包啊，代码随便跑一下，就能轻轻松松知道多少时间占了多少内存啊，算法的效率不就轻松对比出来了么？

小希：。。。。

two羊吐森破，吃葡萄不吐葡萄皮！

你们说的这种主流叫做事后分析法。

简单来说，就是你需要提前写好算法代码和偏好测试数据，然后在计算机上跑，通过最后得出的运行时间判断算法时效的高低水平，这里的运行时间就是我们日常的时间。

我且不用 “万一你费劲心思写好的算法代码本身是个很糟糕的写法” 这种理由反驳你，事后统计法本身存在缺陷，它并不是一个对我们来说有用的度量指标：

首先，事后统计法太依赖计算机的软件和硬件等性能。代码在 core i7处理器 的就比 core i5处理器的运算速度快，更不用说不同的操作系统，不同的编程语言等软件方面，就算在同一台电脑上，前面的条件都满足，当时的内存或者 CPU 的使用率也会造成运行时的差异。

举个例子，考察对全国人口普查数据的排序 $n=10^{9}n=10^9$，使用冒泡排序$(10^9{)}^2(10^9)^2$

对于普通电脑(1GHz $10^{9}10^9$ flops)来说，大约需要$10^{9}10^9$秒(30年)。

对于天河1号超级计算机(千万亿次 = 1P， $10^{1}510^15$ flops)，大约需要$10^{3}10^3$秒(20分钟)。

再者，事后统计法太依赖测试数据集的规模。同样是排序算法，你随便整 5 个 10 个数排序，就算最垃圾的排序，也看起来很快跟火箭一样，不好意思，那 10w个 100w个，那这些算法的差距就很大了，而且同样是 10w 个 100w 个数，顺序和乱序的所花费时间也不等。

那问题来了，到底测试数据集选多少才合适？数据的顺序如何订好多才行？

说不出来了叭？

可以看出，我们需要一个不依赖性能和规模等外力影响就可以估算算法效率，判断算法优劣的度量指标，而复杂度分析天生就是干这个的，为了能自己分析，所以你必须理解要掌握

时间复杂度

算法的运行时间

对于某一问题的不同解决算法。运行时间越短算法效率越高，相反，运行时间越长，算法效率越低。

那么如何估计算法复杂度？

所有人撤退，我们很熟悉的大 O 闪亮登场！

大佬们甩掉脑阔上最后一根秀发的才发现，当用运行时间去描述一个算法快慢的时候，算法中执行的总步数显得尤为重要。

因为这只是估算，我们假设每一行代码的运行时间都为 Btime(一个比特时间),那么算法的总的运行时间 = 运行的总代码行数。

下面我们看一段简单的代码。

代码1

//python

def longgege_sum (m);
      sum = 0;
      
      for longgege in range(m);
            sum += longgege
        return sum;    

在上面假设的情况下，这段求累加和的代码总的运行时间是多少呢？

第二行代码需要 1 Btime 的运行时间，第 4 行和第 5 行分别运行了 m 次， 所以每个需要 m*Btime 的运行时间，所以总的运行时间就是(1 + 2m)*Btime。

若我们用 S 函数来表示赋值语句的总运行时间，所以上面的时间可表达成 S(m)=(1 + 2m)*Btime, 说人话就是"数据集大小”为 m, 总的步数为 (1+2m) 的算法执行时间为 S(m)"。

上面的公式得出，S(m) 和总步数是成正比关系，这个规律很重要的，告诉了一个易懂的趋势，数据规模和运行时间之间有趋势!

可能你对数据规模还是没有概念

类比下

对于我们现在的家用计算机，如果想在1s之内解决问题： O($n^{2}n^2$) 的算法可以处理大约 $10^{4}10^4$ 级别的数据 O(n) 的算法可以处理大约 $10^{8}10^8$ 级别的数据 O(nlogn) 的算法可以处理大约 $10^{7}10^7$ 级别的数据

大 O 表示法

所谓男人有多快，女人有多爱

嗯？

就是，那个算法表示有多快。好你个 渣男，你不是说算法代码真正的运行时间，是代表一种趋势吗，是的，这种趋势随这数据集的规模越大，这种规模记作 O(f(n))。

什么是大O

很多铁子说时间复杂度的时候你都知道O(n), O($n^{2}n^2$), 但是说不清什么是大O

算法导论给出的解释：大O用来表示上界的，上界意思说对任意数据输入的算法最坏情况或叫最长运行时间。

拿插入排序来讲，它的时间复杂度我们都说是 O(n^2), 假如数据本来有序的情况下时间复杂度是 O(n),也就对于所有输入情况来说，最坏是 O(n^2) 的时间复杂度，所以称插入排序的时间复杂度为O(n^2)。

就是想告诉你，同一个算法的时间复杂度不是一成不变的，和输入的数据形式依然有关系，数据用例不一样，时间复杂度也是不同的，这个要铭记住。还有平时面试官和我们探讨一个算法的实现以及性能，指的通常是理论情况下的时间复杂度。

铁子：我读书少，你可别骗我，你这还是有些抽象啊，而且你这适用所有的算法吗，未必吧

小希：你很有精神，你知道前 n 项和怎么算不，

铁子：这个我们初中老师讲过的，等差可以算

小希：你就看好下面，这段码

举栗子

//计算1+2+3+....+n的和
int sum=0

for(int i=1; i<=n; i++){
   sum+=i
}

可以看到循环了 n 次吧，所以时间复杂度就是O(n), 即时间复杂度就是本程序计算的次数。

假如我们自己修改后的运行次数函数中，我们只去保留最高阶项

如果最高阶存在且不是 1，则去除与这个项相乘的常数，是如下表达式：

2n^2+3n+1 ->n^2

所以时间复杂度为 $n^{2}n^2$ 你可能疑问，为啥会去掉这些值，请看下图 当计算量随着次数原来越大的时候，n 和 1 的区别不是太大，而 $n^{2}n^2$曲线 变得越来越大，所以这也是 2$n^{2}n^2$+3n+1 -> $n^{2}n^2$ 最后会估量成 $n^{2}n^2$ 的原因,因为 3n+1 随着计算次数变大，基本可以忽略不计。

铁子：就这，你来个稍微复杂点的吧

安排

//利用sums方法求三部分和
//java
public static int sums(int n) {

int num1 = 0;
for(int longege1 = 1; longege1 <= n; longege1++){
            num1=num1+longege1;
}

int num2 = 0;
for(int longege2 = 1; longege2 <= n; longege2++){
     for(int i = 0; i <= n; i++) {
            num2=num2+longege2;
     }
}

int num3 = 0;
for(int longege3 = 1; longege3 <= n; longege3++){
     for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            num3=num3+longege3;
        }
     }
}

return num1 + num2 +num3;
}

上面这段是求三部分的和，经过之前的学习应该很容易知道，第一部分的时间复杂度是 O(n), 第二部分的时间复杂度是 O($n^{2}n^2$), 第三部分是O($n^{3}n^3$)。

正常来讲，这段代码的S(n)=O(n)+O($n^{2}n^2$)+O($n^{3}n^3$),按照我们按“主导”部分，显然前面两个兄弟都直接帕斯掉，最终S(n)=O($n^{2}n^2$)。

通过这几个例子，聪明的铁子们坑定会发现，对于时间复杂度分析来说，只要找出“主导”作用的部分代码即可，这个主导就是最高的那个复杂度，也就是执行次数最多的那部分 n 的量级。

剩下的就是多加练习，有意识的多去练多去想，就可以和我一样 帅气稳啦。

好吧

我来介绍几种爹，不是，几种阶~

常数阶 O(1)

function test($n){
    echo $n;
    echo $n;
    echo $n;
}

没有循环的，不管 $n 是多少，它只运行 3 次，那么时间复杂度就是O(3),取为O(1)

线性阶 O(n)

for($i=1;$i<=$n;$i++){
    $sum+=$i
}

熟悉的平(立)方阶：o($n^{2}n^2$)/o($n^{3}n^3$)

$sum=0;
for($i=1;$i<=$n;$i++){
    for($j=1;$j<$n;$j++){
    $sum+=$j
    }
}

两次循环，里面循环执行了 n 次，外层循环也执行了 n 次，所以时间复杂度为O(n^2),立方阶一样

特殊平方阶：O($n^{2}n^2$/2+n/2)->O($n^{2}n^2$)

for(){
    for(){
    .....            ----------->n^2
    }
}
                                  +
for(){
                     ------------> n
}

                                  +
                                 
echo $a+$b         --------------> 1

所以整体上计算次数为 n^2+n+1,我们算时间复杂度为O(n^2)

对数阶：O(log2n)

int longege = 1 

while(longege < m) {
    longege = longege * 2;
}

还是根据之前讲的，我们先找“主导”，在里面主导就是最后一行，只要算出它的时间复杂度，这段的时间复杂度就知道了。

这段说人话就是，乘多少个 2 就会 >= m?

假设需要 y 个，那么相当于求：

所以上述代码的时间复杂度应该为O(log₂m)。

但是这种对数复杂度来说，不管你是以2, 3为底，还是以 20 为底，通通记作(logn)

这就要从对数的换底公式说起。

除了数据集规模会影响算法的运行时间外，“数据的具体情况”也会影响运行时间。

我们来看这么一段代码：

public static int find_word(int[] arr, String word) {

                int flag = -1;
                for(int i = 0; i <= arr.length; i++) {
                        if(arr[i] == word) {
                              flag = i;
                        }
                        
                        break;
                }
                
                return flag;
} 

上面这段简单代码是要求字符变量 word 在数组 arr 中出现的位置，我用这段来解释“数据的具体情况”是什么意思。

变量 word 可能出现在数组 arr 的任意位置，假设 a=['a', 'b', 'c', 'd']:

• 当 word = 'a', 正好是列表中的第 1 个，后面的不需要在遍历，那么本情况下的时间复杂度是O(1)。
• 当 word = 'd' 或者 word='e', 这两种情况是整个列表全部遍历完，那么这些情况下的时间复杂度是O(n)。

根据不同情况，我们有了最好情况时间复杂度，最坏情况时间复杂度和平均情况时间复杂度这三个概念。

下面看一段代码，我们分别从最好和最坏的情况下去分析其时间复杂度。

// n 表示数组 array 的长度
int find (int[] array, int n, int x) {
    int i = 0;
    int pos = -1;
    for (int i=0; i < n; i++) {
        if (array[i] == x) {
            pos = i;
        }
    }
    
    return pos;
}

这段代码的功能是，在一个无序的数组中，查找变量 x 出现的位置。如果没有找到就返回 -1。笼统的分析一下：核心代码执行了 n 次，所以其时间复杂度是 O(n)，其中，n 代表数组的长度。

代码简单优化一下：可以在中途找到符合条件的元素时，提前结束循环。

// n 表示数组 array 的长度
int find (int[] array, int n, int x) {
    int i = 0;
    int pos = -1;
    for (; i < n; i++) {
        if (array[i] == x) {
            pos = i;
            break;
        }
    }
    return pos;
}

优化完之后的代码就不能简单粗暴的说其时间复杂度就是 O(n)了。因为，遍历可能在数组下标为 0 ~ n-1 中的任何一个下标所指向的元素中结束循环，是不是很神奇

继续往下分析：

1. 假设，数组中第一个元素正好是要查找的变量 x ，显而易见那时间复杂度就是 O(1)。

2. 假设，数组中不存在变量 x ，那我们就需要把整个数组遍历一遍，时间复杂度就成了 O(n)。

所以，在不同的情况下，这段代码的时间复杂度是不同的。

等我踹口气

嗯~

还有个问题

这几个概念从我相信你从字面意思也能理解，最好时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。对应假设1。时间复杂度就是 O(1)。

同理，最坏时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。对应假设2。时间复杂度就是O(n)。

平均时间复杂度

首先先来说它，又叫“加权平均时间复杂度”，为什么叫加权呢？是不是很奇怪，因为，通常计算平均时间复杂度，需要把概率考虑进去，也就是，我们计算平均时间复杂度的时候，需要一个“加权值”，来真正的计算平均时间复杂度。

我们代码整个例子，对平均时间复杂度进行分析：

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {

  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = I;
       break;
    }
  }
  
  return pos;
}

代码很简单，表示在一个数组中，要找到 x 这个数，最好复杂度是 O(1), 最坏是 O(n)。

那平均复杂度是怎么计算呢？

先说简单的平均值计算公式：

上面的代码，所有查找 x 的时间相加：1 + 2 + 3 +······ + n + n (这个 n 表示当 x 不存在时遍历 array 需要的次数) ， 另外，需要查找的次数为 n + 1 次，那么结果就是：

代入大 O 表达式，结果是 O(n)。

这个公式表达的是：计算所有可能出现的情况之和，然后除以可能出现的情况的次数。说白了，这是一个绝对平均的结果。表示每个结果都可能出现 n + 1 次。

这是一个较为粗暴的假设。

如果稍微使用一个简单的概率来计算呢？

这里有 2 个概率：

x 变量是否在数组中的概率，有 2 种情况—— 在与不在，所以，他的概率是 1/2. x 变量出现在数组的概率，有n 种情况，但只会出现一次，所以是 1/n. 我们把两个概率进行相乘，结果是 1/(2n). 这个数，就是“加权值”。

如何使用加权值对上面代码的“复杂度”进行计算？

然后，我们在这公式上把 (n + 1)换成“权重”：也就是 1/2n。

结果为 3n + 1 / 4 。这个也就是“加权后的平均时间复杂度”，表示，执行了 1 + 2 + ···· + n + n 次的“加权平均值”。

如果使用大 O 表示法，去除系数，常数，低阶，那么他的最终结果就是 O(n)。

可以看到，前者使用的是分母没有做任何权重的措施，仅仅是简单的 n + 1，而后者，我们做了简单的权重计算，认为出现的概率不是 n + 1，而是 1/2n。

可以说，加权值，是为了在前者的基础上，，目的是更加的准确。也就是说，要计算准确的平均时间复杂度，就需要准确的计算这个“权重值”，而权重值会受到数据范围，数据种类影响。因此需要在实际操作中，进行调参。

简单来说，就拿 “x 变量是否在数组中的概率” 这个值来说，不一定是 1/2 ，如果有这样一组数据{y, s, f, f, g, x, g, h}， 那么，他的概率还是 1/2吗，实际上只有 1/8，所以，还是得根据实际情况来。

均摊时间复杂度

啊这，听起来和平均时间复杂度有点熟悉呢。但是均摊时间复杂度的应用场景比平均时间复杂度更加特殊、更加有限。下面看一段代码：

//array 表示一个长度为 n 的数组
//代码中的 array.length 就等于 n

static int[] array = new int[]{1, 2, 3, 4, 5};
static int count = 2;    
public static void insert(int val) {

      // 数组没有空闲空间的情况
      if (count == array.length) {
          int sum = 0;
          for (int i = 0; i < array.length; i++) {
              sum = sum + array[i];
        }
        array[0] = sum;
        count = 1;
        System.out.println("array.length:::" + array.length + "sum:" + sum);
    }
    
        // 数组有空闲空间的情况
        array[count] = val;
        count++;
          System.out.println("count!=array.length:" + array.length + ",,,count::" + count);
    for (int i = 0; i < array.length; i++) {
    
        System.out.println("array[" + i + "] = " + array[i]);
    }
}

上面实现了向一个数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数组插入数组。

现在分析一下这段代码的时间复杂度，最理想的情况下，数组中有空闲空间，我们只需要将数据插入到下标为 count 的位置就可以了，所以最好情况时间复杂度为 O(1)。最坏的情况下，数组中没有空闲空间了，我们需要先做一次数组的遍历求和，然后再将数据插入，所以最坏情况时间复杂度为 O(n)。

接着我们按上面的方法分析一下平均时间复杂度。假设数组的长度是 n ，根据插入数据的位置不同，我们可以分为 n 种情况，每种情况的时间复杂度是 O(1)。此外，还有一种 ：“额外” 的情况，就是在数组没有空闲空间插入一个数据，这个时候的时间复杂度是 O(n)。而且，这 n + 1 中情况发生的概率是一样的，都是 1/(n + 1)。

其实，这个例子里的平均复杂度分析并不需要这么复杂，不需要使用概率的知识。我们先来对比一下这个 insert() 的例子和上面的 find() 的例子，二者的区别如下：

• 区别一：

首先，find() 函数在极端情况下，复杂度才为 O(1)。但 insert() 在大部分情况下，时间复杂度都为 O(1)。只有个别情况下，复杂度才比较高哦，为 O(n)。这是两者间的第一个区别。

• 区别二：

对于 insert() 函数来说， O(1)时间复杂度的插入和 O(n)时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 O(n) 插入之后，紧跟着 n - 1 个 O(1) 的插入操作，循环往复而已。

所以，针对这样一种特殊场景的复杂度分析，我们不需要像之前平均复杂度分析方法那样，找出所有的输入情况及相应的发生概率，然后再计算加权平均值，这种就没必要。

针对这种特殊的场景，我们引入一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度叫做均摊时间复杂度。

那究竟如何使用摊还分析法来分析算法的均摊时间复杂度呢？

继续看这个 insert() 的例子。每一次 O(n) 的插入操作，都会跟着 n - 1次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n - 1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路，可以吧？

对一个数据结构进行连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候我们就可以把这一组操作放在一起来分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。 而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就约等于最好情况时间复杂度。

总之，均摊是平均时间复杂度的极限情况

均摊时间复杂度可能不是很好理解，尤其是与平均时间复杂度的区别。但是，我们可以将其理解为一种特殊的平均时间复杂度。最主要的还是应该掌握它的分析方法，这种思想而已。

之所以引入这几个复杂度的概念，是因为，我们在同一段代码，在不同输入的情况下，复杂度量级有可能是不一样的。在引入这几个概念之后，我们可以更加全面的表示一段代码的执行效率。

平时大家更多的关心是最好的时间复杂度，这没错，提高时间效率吗没错

但

我觉得更关心最坏情况而不是最好情况，理由如下：

（1）最坏情况它能给出算法执行时间的上界，这样可以确信，无论给什么输入，算法的执行时间都不会超过这个上界，这样为比较和分析心里有个底。

（2）最坏情况是种悲观估计，但是对于很多问题，平均情况和最坏情况的时间复杂度相差不多，比如插入排序这个例子，平均情况和最坏情况的时间复杂度都是输入长度n的二次函数。

空间复杂度

空间复杂度跟时间复杂度相比，你需要掌握的内容不多。 也是一样，它也是描述的一种趋势，只不过这趋势是代码在运行过程中临时变量占用的内存空间。

嗯？临时吗

就要从代码在计算机中的执行摆起啦。

代码在计算机中的运行的存储占用，主要 分成 3 部分

• 代码本身所占用的
• 输入数据所占用的
• 临时变量所占的

前两个它自己就是要必须占用空间，与代码的性能就没关系，所以最后衡量代码的空间复杂度，只关心在运行过程中临时占用的内存空间。

怎么算？

空间复杂度记作R(n), 表示形式与时间复杂度 S(n) 一致。

分析下

下面我们用一段简单代码来理解下空间复杂度。

//python
def longege_ListSum(n):

      let = []
      for i in range(n):
                let.append(i)
          
      return let
      

上面这段中明显有两个临时变量 let 和 i

let 是建了一个空列表，这个列表占的内存会随着 for 循环的增加而增加，最大到 n 结束，所有呢，let 的空间复杂度是 O(n), i 是存元素位置的常数阶，和规模 n 已经没有关系了，所以这段代码的空间复杂度为 O(n)。

我们再来看下 它

O($n^{2}n^2$)

//java
public static void longege_ListSum(n) {

    int[] arr1 = new int[0];   
        for(int i=0; i<=n; i++) {
            int arr2 = new int[0];
            
            for(int j=0; j<=n; j++) {
                  arr1.apend(arr2);  
          }
  }
  
        return arr1;
}

还是一样的分析方式，很明显上面这的代码手动创建了一个二维数组 arr1, 一维 占用 $n^{2}n^2$, 所以它就是这段代码的空间复杂度啦。

那二分法是多少

int select(int a[], int k, int len)
{
     int left = 0;
     int right = len - 1;
     while (left <= right)
     {
          int mid = left + ((right - left) >> 2);
          if (a[mid] == k)
          {
              return 1;
          }
          else if (a[mid] > k)
          {
              right = mid - 1;
          }
          else
          {
              left = mid + 1;
          }
     }
     return NULL;
}

代码中的 k、len、a[] 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

顺便说下

在最坏的情况下循环x次后找到, n / ($2^{x}2^x$)=1; x=log2n;它的时间复杂度就是log2n。

在斐波那契数求空间复杂度的过程中，需要去考虑函数栈帧的过程，比如当我们求第五个斐波那契数的时候，这时候需要先开辟空间存放第四个数，然后再开辟空间存放第三个数；当开辟空间到第二个和第一个数的时候，第三个数得到结果并返回到第四个数中，第四个数的值已知后返回到第五个数，过程里面，最大占用空间即为层数减一。

开辟空间的大小最多等于层数+1，也就是说求第N个斐波那契数，空间复杂度即为O（N）。 

递归算法的时间复杂度

1）一次递归调用,如果递归函数中，只进行一次递归调用，并且递归深度是 depth, 那么每个递归函数，它的时间复杂度为 T, 则总体的时间复杂度为O(T * depth)。

比如说，二分搜索法的递归深度是 logn（每次都是对半分）,则复杂度是O(Tlogn)

总结个公式就是，递归的时间复杂度=递归总次数 * 每次递归的次数，空间复杂度=递归的深度（即树的高度）

2）两次递归调用（关注递归调用次数） 我们先看下面这个例子

int f(int n) {
         assert(n >= 0);
         
         if(n == 0)
             return 1;
          else
             return f(n-1) + f(n-1); 
}

怎样才能知道它的递归次数呢，我们可以画一棵递归树，再把树的节点数出来

可以看到，这是指数级的算法，很慢很慢的！但这在我们的搜索领域是有很大的意义的。

但是我们的高级排序算法如，归并，快排也是2次递归调用，但时间复杂度只有O(nlogn)级别，那是因为

1）上面的深度为n，而高级排序的深度都只有logn

2）在高级排序算法中我们在每个节点处理的数据规模是组件缩小的。

斐波那契数列的优化

斐波那契数列循环算法：
 
//时间复杂度：O(n)
//空间复杂度：O(1)
long long Fib(long N)
{
	long long  first = 1;
	long long second = 1;
	long long  ret = 0;
	int i = 3;
	for (; i <= N; ++i)
	{
		ret = first + second;
		first = second;
		second = ret;
	}
	return second;
}
int main()
{
	printf("%u\n",Fib(50));
	system("pause");
	return 0;
	
}

//斐波那契数列递归算法：
//时间复杂度: O(2^n)
//空间复杂度：O（n）
long long Fib(long long N)
{
	return (N < 3) ? 1 : Fib(N - 1) + Fib(N - 2);
}
 
int main()
{
	printf("%u\n",Fib(1,1,50));
	system("pause");
	return 0;
}

注意： 斐波那契数列的时间复杂度为二叉树的个数； 斐波那契数列的时间复杂度为函数调用栈的次数即二叉树的深度。

//斐波那契尾递归算法：（优化）
//时间复杂度：O（n）
//空间复杂度：O(n)
long long Fib(long long first,long long second,int N)
{
	if (N < 3 )
	{
		return 1;
	}
	if (N == 3)
	{
		return first + second;
	}
	return Fib(second,first+second,N-1); 
}

使用矩阵乘方的算法再次优化斐波那契数列算法。

 static int Fibonacci(int n)
      {
           if (n <= 1)
            return n;
 
      int[,] f = { { 1, 1 }, { 1, 0 } };
       Power(f, n - 1);
 
       return f[0, 0];
   }

    static void Power(int[,] f, int n)
    {
      if (n <= 1)
        return;
 
       int[,] m = { { 1, 1 }, { 1, 0 } };

     Power(f, n / 2);
       Multiply(f, f);

       if (n % 2 != 0)
        Multiply(f, m);
     }

   static void Multiply(int[,] f, int[,] m)
   {
      int x = f[0, 0] * m[0, 0] + f[0, 1] * m[1, 0];
     int y = f[0, 0] * m[0, 1] + f[0, 1] * m[1, 1];
       int z = f[1, 0] * m[0, 0] + f[1, 1] * m[1, 0];
       int w = f[1, 0] * m[0, 1] + f[1, 1] * m[1, 1];

      f[0, 0] = x;
       f[0, 1] = y;
       f[1, 0] = z;
     f[1, 1] = w;
     }
     

优化之后算法复杂度为O(log2n)。

请背下来

算法刷题过程中，我们会遇到各种的时间复杂度，但就算你代码变出花来，几乎也逃不出下面几种常见的时间复杂度。

上表中的时间复杂度是由上往下依次增加，所以 O(1) 效率最高，O(n) 和 O($n^{2}n^2$) 这两个前面已经说过了，上表最后一个效率低的离谱，以后要是不幸碰到我了在提一下，就不细说。

可能有些朋友还是疑惑，现在计算机硬件性能越来越强了，我们为啥还这么重视时间复杂度呢？

问的很好，我们可以用几个栗子来对比下，看下之间它们有多大的差距。

有100个人站在你面前，你一眼就发现了你喜欢的她。

如果换成10000个，结果并没有什么区别。

这就是 O(1) 有100个人站在你面前，你得一个一个看过去，才能找到你的女神。无论你用什么顺序看，我总有一种办法，把你的女神放在你最后看到的那个。如果换成10 000个，你就有了100倍的工作量。

这就是O(n)

假如现在有100个人站在你面前，脸盲的你得两两结对、一对一对观察，才能找到唯一的一对双胞胎。同上，我总是可以把双胞胎放在你最后找到的一对。你至多一共要观察 4950 对。

如果换成10000个，那就是49 995 000对，也就是 10100 倍的工作量

这就是O(n²)

有128个人站在你面前，你要把他们按照高矮排序——我们假设用归并来解——你先把他们分成两个64人的大队，每个大队分成两个32人的中队，每个中队分成……直到最后每一个“小小…小队”只剩一个人。显然，一个人一定是已经排好序的。

然后反向操作，将刚刚拆分的队伍合并起来。合并队伍的时候，由于已经排好序，只需要取出两队排头进行比较，就找到了最矮的一个，取出来——如此进行下去，合成的两倍大的队伍也将是有序的。显然，这个合并操作，是O(n)的。总共的比较次数，不会超过两个队伍的总人数。

最后的问题只是，有多少次“分割-合并”操作。每次分割数量都减半，很明显是 7 次。由此看来，大致需要执行 7×128 次操作。

这就是O(nlogn)

不同的时间复杂度，差距是明显的，好了，下面给出你需要铭记在心里的

数据结构的时间复杂度

排序算法的时间复杂度

算法稳定性什么意思？如果排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同，我们说算法具有稳定性，有什么意义呢？如果排序的算法是稳定的，第一个次排序的结果和关键字段可以为第二个次排序所用。

最后，算法和性能的关系，衡量一个算法的好坏，主要通过数据量大小来评估时间和空间，这些最后都直接会影响到程序性能，一般空间利用率小的，所需时间相对较长。所以性能优化策略里面经常听到 空间换时间，时间换空间这样说法。

到这里，复杂度分析就全部讲完啦，只要你认真看完这篇文章，相信你会对复杂度分析有个基本的认识。复杂度分析本身不难，记得平时写代码的时候遇到问题有意识多估计一下自己的代码，感觉就会就会越来越熟悉的。

这是算法的首篇，写完真心不容易，手痛哈哈，希望开了好头，码字不易，铁子们多多支持呀，点赞在看转发么么哒呀。

我是小希，咱们下次见~