时间效率高 存储低、
算法效率因素
1.算法
2.编译产生的代码质量--高级语言转二进制
3.输入规模
4.机器速度
2.衡量算法的几个维度
时间复杂度和空间复杂度 与最高次项的n的阶数，不需要关心乘数和加数
2.1时间复杂度：执行次数=监禁时间复杂度=时间复杂度O(n)
攻略
1.常熟1取代运行时间中所有常数
2.只保留最高阶
3.最高阶存在，不是1，去除这个项的常数，2n O(n)
常数阶 for()
平方阶for(for()) O(n^2)
for(int i=0;i<n;i++)(for(j=i;j<n;j++))() O(n^2)
对数阶2^x=n x =log(2)n O(logn)
嵌套函数 O(n) *O(n)=O(n^2)
常见时间复杂度
常数 O(1)
线性 O(n)
平方O(n^2)
对数O(logn) 3log(2)n+4
nlogn阶O(nlong) 3nlog(2)n
立方O(n^3)
指数 O(2^n)
平均运行时间
最坏运行时间
2.2空间复杂度：
时间换空间，空间换时间
S(n)=O(f)(n))
一般算复杂度一般是时间复杂度
3.线性表
List:由0个或多个数据元素组成的有限序列
特点：有序，1前驱1后继元素，普通元素有1前驱1后继，元素有限
3.1线性表顺序存储结构--数组
内存空间中，依次放入数据。
根据下标就可以获取元素，获取元素的时间复杂度O(1)
线性存储也是随机存储结构
增删改的伪代码
删除的最后的时间复杂度O(1),最坏的时间复杂度O(n)所有的线性表都移动
线性表 增删 时间复杂度O(n)
改查 时间复杂度O(1)
线性表顺序存储结构结论：线性表适合元素个数固定，不要经常插入和删除元素，更多的操作是存取数据
线性表顺序存储优缺点：
优点：无需为元素之间逻辑关系增加存储空间；可以快速读取表中任意位置元素
缺点：增删元素需要移动大量数据；难以确定线性表顺序存储结构的容量；容易造成存储空间碎片
3.2链式存储结构
链式存储结构需要存储元素的数据域，还需要一个紧接着的位置存储后继位置，即指针域
两部分信息组成数据元素成为存储映像，称为结点。
n个结点连接成一个链表，即为线性表的链式存储结构。此链表的每个节点只包含一个指针域，称为单链表。
头指针：指向链表第一个节点的指针（可能是头结点，也可能是第一个数据节点），可以给链表冠名，链表必须有头指针。
头节点：链表第一个节点，数据域不存储数据，但可以存放链表长度（可选），不是必备节点。
最后一个节点，指针域为空
3.2.1单链表的读取
时间复杂度O(n)，核心思想：工作指针右移。
3.2.2单链表插入
链表中i位置插入节点思路：
创建节点指向链表头结点。j<1开始遍历链表；
若遍历结束没有i，报错，
若找到第i个节点p(i)，创建一个新节点s，将数据e放入s->data(e),
s->next =p->next
p->next=s
3.2.3单链表删除
找到要删除的i节点，p(i-1)指针改为p(i)指针
单链表的增删节点时间复杂度O(1)（不考虑遍历的情况）
查找时间复杂度O(n)
头插法 尾插法
线性表总结
数组：增删不多，元素节点固定。内存整块申请，查找快O(1)，增删慢O(n)
单链表：节点变化多，不固定长度。增删块O(1)，查找慢O(n)
单链表增删快，可能需要遍历，然后找到某个节点，所以要注意应用场景。
4.静态链表
用数组来代替链表
image.png
游标的屁股指向头，头部指向尾。
游标的MAXSIZE-1指向，第一个有数据的下标
游标的头指向，最后一个有数据的下标
游标指向下一个有数据的节点。
4.1静态链表插入
需求：在A后边加上B元素
首先找到游标的第一个，指向的是最后一个元素，
然后再最后一个元素后插入新元素
修改：找到A后，修改A的游标指向
修改游标第一位为B的下标。
4.2静态链表删除
需求：刚插入的B后边删除C，C回收作为备用链表
首先，C的游标给B，C的数据清空，C的游标赋值为第一个游标，第一个游标赋值为删除C的下标。
优点：插入删除，只需要修改游标，改进了线性表顺序存储结构需要大量移动元素的缺点。
缺点：没有解决长度难以确定的问题
失去了顺序存储的索引优势。
题目：快速找到未知长度单链表的中间长度
普通题解：遍历一遍，长度L，在遍历一遍到2/L，O（L+1/2L）=O(3/2L)
快慢指针：两个指针，快的指针是慢的指针移动两倍，开始两个指针都指向链表头部。
O(1/2L)
5.循环链表
最后一个节点的指针指向头结点的索引。
循环 空链表：头结点的指针指向自己
6.约瑟夫问题
5.1判断单链表是否有环
1590978941(1).jpg
思路1：快慢指针，如果两个指针到同一个节点步数不相同，则有环
思路2：双指针，双遍历，如果到同一个节点
7.双向链表
双向链表比单向链表多了一个prior指针，一个数据域，两个指针域。
节点b，的next指针域指向c节点data，节点b的prior指向a的data
网友评论