衡量算法性能的量级标准：算法复杂度

今天开始数据结构的学习！作为一大重点，拿出态度很重要，想要真实掌握，博客笔记自然少不了！重点全部上色！避免疏忽

下面我们从0基础开始学习今天的第一节！不用担心看不懂，拒绝枯燥的理论概念！   

目录

对“算法”的理解

“算法复杂度”概念理解

        一  时间复杂度的表示与计算

                       一.1  时间复杂度实例讲解

              一.2  “约会”预期管理类时间复杂度

              一.3  “约会”预期管理类时间复杂度实例讲解

              一.4  时间复杂度的意义

二  空间复杂度的表示与计算 

              二.1  空间复杂度实例讲解

---

对“算法”的理解

算法简而言之，就是解决问题的步骤跟指令，通过一系列操作，从而达到预期的结果

“算法复杂度”概念理解

哈是算法复杂度？

概念：度量算法性能优劣的一个量级说明

度量算法主要从两个方面来考虑：时间复杂度    空间复杂度

时间复杂度作用：体现执行这个算法所需要的计算工作量（下面是完整概念）

比如：对2个算法进行比较，若算法A较算法B更加快，此时指它的时间复杂度更好 

空间复杂度作用：体现执行这个算法所需要占用的额外的内存空间大小（下面是完整概念）

下面我们分别来进行讲解！ 

一  时间复杂度的表示与计算

表示：首先它的表示用大O符号表示（O（n）），这个n（下面参考例题详解！）表示这个问题的             一个工序规模次数 ，O（n）也叫大O表示法

计算规则：

                  1：用常数1来取代运行时间中所有加法常数

                  2：只要高阶项，不要低阶项

                  3：不要高阶项系数

常见的时间复杂度（复杂度由低到高）：

                                                                  O（1）             常数阶

                                                                  O（n）             线性阶

                                                                  O（n^2）         平方阶

                                                                  O（logn）        对数阶

                                                                  O（nlogn）      nlogn阶

                                                                  O（n^3）         立方阶

                                                                  O（2^n）         指数阶

画图演示：

一.1  时间复杂度实例讲解

                                                                          实例1

第一步：我们计算出这个工程的工序次数是 2*N+10 次

第二步：根据计算规则进行删除

                                                    只要高阶项，不要低阶项，去除10，首先得到：2*N

                                                    不要高阶项系数，去除2，最后得到：N

第三步：得出最终结果，Func2的时间复杂度为 O（N）

                                                                      实例2

第一步：计算这个工程的执行工序，得到：M+N  次

第二步：根据计算规则进行删除更改：

                                                             因为M与N都是未知数，因为最高阶阶数相同，也无常数                                                                   故全部保留

第三步：得出时间复杂度：O（M+N）

                                                                      实例3      

第一步：计算这个工程的总工序，得到100  次

第二步：根据计算规则进行更改与删除：

                                                               用常数1取代所有加法常数，100改为1，最终得到1

                                                               注：这个“1”代表常数次，不是代表1次 

第三步：得到时间复杂度：O（1）

一.2  “约会”预期管理类时间复杂度

难道跟“约会”有关吗？没错没错！下面如果是你和你的对象约会，你会选择哪个时间点？                最早：下午17：00

                                                            大概：下午19:00

                                                            最迟：下午20:00

我们来分析一下，因为这只是一个引入，所以无法符合每个人的想法啊！

如果我们把对每件事的期望尽量拉小，那么当这件事不管完没完成，对你的打击也就越小！

如果失败：那么我的期望也没那么高，管的他呢！

如果成功：带给我的期望是不是更多一些！

下面我们针对非直接性（需要分情况考虑）的对时间复杂度的计算：

另外一些时间复杂度存在几种考虑情况：比如计算：什么时候可以从一堆字符串找到一个对应字符

有以下几种情况：

                            直接一次找到，这属于最好情况（下界）

                            找到末尾才找到，这属于最坏情况（上界）

                            最坏与最好平均下来，就是平均情况

那么我们假设一个长为N的字符串，对应几种情况分别是：1次

                                                                                             N次

                                                                                             N/2次

在实际情况中一般关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O（N），取最坏情况

一.3  “约会”预期管理类时间复杂度实例讲解

                                                                       实例1

第一步：得到这个问题的最坏工序次数为 7 次

第二步：根据计算规则进行删除与更改：

                                                                   用常数1取代所有加法常数，7改为1

第三步：得到Srchr的时间复杂度为 O（1）

                                                                     实例2

第一步：计算这个问题的最坏情况下执行次数，为N^2（也就是N的平方）

第二步：根据计算规则进行删除与更改：

                                                                与三条规则不冲突，不用更改

第三步：得到它的时间复杂度为 O（N^2）

 

                                                                   实例3

二分查找涉及数学逻辑，下面配有演示！

 第一步：计算这个问题最坏情况工序为 logN（也就是log以2为底的N的对数）

第二步：根据计算规则删除与更改：

                                                         与三条规则不冲突，直接保留

第三步：得出时间复杂度为 O（logN）

我们看数学演示计算过程：假设N是数组个数，x表示最坏查找数

查询次数	记录
1	N/2
2	N/2/2
3	N/2/2/2
x	N/2^x

我们发现：每查询一次，就需要除一次2

                  那么查询x次，就表示N/2^x

                  有2^x=N（注意：查一次有一个2，那么查了x次，就是2^x，数组有N个元素，那么最                      坏情况就是N=2^x）

                  那么最坏查找数  x=log2N

由于：log以2为底的N的对数不好写这个底数，所以规定：凡是以2为底的对数可以直接写为logN

注：只适用于以2为底的对数 可以写为  logN（底数2可以不写）

                                                                     实例4

（斐波那契数的计算，下图配有数学解析） 

 第一步：计算这个问题的最坏工序次数：

第二步： 根据计算规则进行删除与更改：

                                                              去除高阶项系数2^（N-1）=2^N * 2^（-1），最终得2^N

第三步：得到时间复杂度 O（2^N

一.4  时间复杂度的意义

学会时间复杂度的计算，可以更理解题目的要求，以及比较平时代码的性能，比如：

我们可以看到上面有时间复杂度的限制，那么我们在写题目时，需要先大概计算一下时间复杂度！ 

二  空间复杂度的表示与计算

空间复杂度我们之前已经大概了解了一下：   运行算法过程中额外占用存储空间大小的量度

表示：与时间复杂度类似，还是用大O表示法：O（n），其中n表示变量个数，n一般等于变量个数+额外开辟次数（不是字节数）

计算：依然遵循时间复杂度的三条原则

注意：函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等等）在编译器期间已经确定好了，因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定

 投机取巧：一般空间复杂度大多是O（1）与O（n）两种情况，遇到其它的概率很小！

下面我们来进行实例讲解！

二.1  空间复杂度实例讲解

                                                                        实例1

第一步：计算图中的变量个数以及看是否额外占用空间

               发现创建了3个变量，并没有额外开创空间（带 i 的循环是在n里面的，所以 i 用的是n开                 辟的那个空间，没有重新开辟）

第二步：按照三条规则重新删除与更改：常数项改为1

                                                                O（3）也就变成了O（1）

第三步：得出空间复杂度为O（1）

      

                                                                           实例2

第一步：分析变量个数与额外开辟空间大小 （变量个数+额外开辟空间）

第二步：计算 额外占用存储空间大小为O（n+1+1）

              按照三个规则进行删除与更改：只要高阶项，不要低阶项，改为O（n） 

第三步：得出空间复杂度 O（n）

                                                                      实例3

第一步：计算变量个数以及额外占用的空间 

每次调用函数都需要开辟空间，一共调用了N+1次 （这个空间的开辟是计算开辟次数，不是字节）

 第二步：根据三条规则进行删除与更改：不要地阶项，只保留高阶项

                                                                  O（N+1）更变为 O（N）

第三步：空间复杂度为 O（N）

                                                                 

以上就是   算法复杂度  的全部讲解了！写的好的话记得一键三连哦！希望每天都是阳光明媚！