2021年07月25 数据结构

发表于 分类于 ， ， Waline： 本文字数： 1k 阅读时长 ≈ 1 分钟

前言

模拟登陆

数据结构

算法

衡量算法的两个指标：

  • 时间复杂度
    • 算法执行了多少时间
      • 看代码执行的次数
        • 只看循环次数
  • 空间复杂度

时间复杂度如何计算

1
2
3
for(int i=0;i<n;i++){
  s=s+n;
}

时间复杂度O(n)，称为线性空间。

lim{f(n)/G(n)}=常量
O(G(n))=

1
2
3
4
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int k=1;k<=j;k++)
  s=s+k*i*j;

算法的复杂度是多少
设置循环变量最大值的情况，i=n，j=i=n,k=j=i=n
所以是n*n*n，算法福再度为O(n^3)

1
2
3
4
int i=1;
while(i<=n){
  i=i*2;
}

假设执行f(n)次数
2^{f(n)}=n

f(n)=log_2{n}
lim_{n->+无穷}{f(n)/G(n)}=常量
所以G(n)可以设置为log_2{n}
所以算法复杂度为O(log_2{n})

空间复杂度

空间复杂度，不计入要处理的数据所占用的空间。
算法中额外使用的空间
循环变量可以不算

主要的存储方式

  • 顺序存储
  • 链式存储
  • 哈希存储
  • 索引存储

前三种存储主要存储在内存中。

索引存储—数据库
主要存储在在硬盘。

顺序存储

链式存储

插入和删除很方便
查找很麻烦。必须从头往后查找

分页显示
先从数据库中读取数据到后端，显示的时候前端在分批请求。

数据结构习题

链表

  • 头插入
    • 输入一组数，建立一个链表
  • 未插入
  • 倒置
    • O(n)时间复杂度实现，(一个循环实现)
      • 头插法实现
      • 尾插罚实现
  • 有序插入
    • 找插入点
      • 插入点在头部
      • 插入点在中间
      • 插入点在尾部
  • 删除
  • 重复的都要删除
  • 两条有序的合并成一条有序的
  • 两个单链表是否有公用节点，返回第一个公用的节点
    • 方法1:从第一个链表找那个取出一个节点，到另一个链表中取查找（O(n^2)）
    • 方法2:算出两个链表的长度，从长的链表开始，去掉长度部分，等到相等的时候，循环2
  • 求链表倒数第n个节点（）
    • 方法1：1个循环统计长度，然后再循环长度-n就是倒数第n个
    • 方法2：使用两个指针,a指向头，b指向第3个，等b走到最后的时候，a就是倒数第3个。
  • 判断链表是否有尾环
    • 使用两个指针，a,b,a走1步，b走2步，如果b等于a，的时候就是有环了
    • 追加提问：并找出环的入口点，在b等于a的时候，一个往前，一个往后，这样就变成了求公共节点了。

明天下午上课