数据结构与算法、网络模型总结

用户头像
2流程序员
关注
发布于: 2020 年 07 月 29 日

基本数据结构

数组

特点:

  1. 存储空间连续

  2. 只能防止相同数据类型

  3. 可随机读写

  4. 中间插入或删除元素时间复杂度O(n)

链表

特点:

  1. 可使用零散的内存空间

  2. 每个元素包含下一个或上一个元素指针

  3. 查找元素时间复杂度为O(n)

  4. 插入和删除元素总体成本比数组低

hash表

数组和链表的组合,可在O(1)时间内访问和增删数据

数组或链表限定操作条件:后进先出。

队列

数组或链表限定操作条件:先进先出。

二叉排序树

定义:

  1. 左子树上所有节点的值均小于或等于它根节点的值

  2. 右子树上所有节点的值均大于或等于它根节点的值

  3. 左、右子树也分别为二叉排序树

特点:

可在O(logn)时间复杂度内查找到元素

缺点:

在最坏情况下会退化为链表,查找时间复杂度提高到O(n)

平衡二叉树和红黑树

两者都可解决二叉排序树左右子树不平衡或退化为链表到问题

平衡二叉树大量增删时,效率低下,而红黑树最多只需要3次旋转就会从新达到平衡

但红黑树的平衡性不如平衡二叉树,故查找效率不如平衡二叉树。

网络模型

阻塞式I/O模型



当进程在等待数据时,若该数据一直没有产生,则该进程将一直等待,直到等待的数据产生为止,这个过程中进程的状态是阻塞的。





非阻塞式I/O模型

在非阻塞式I/O模型中,当进程等待内核的数据,而当该数据未到达的时候,进程会不断询问内核,直到内核准备好数据。





I/O多路复用

由一个线程轮询,当有数据可读或可写时,调用相应的处理函数。

常用的IO多路复用技术有两种,select和epoll。

select特点是线程轮询所有队列中的socket,逐个处理,当队列中socket数量过多时,轮询消耗时间较多。

epoll则是通过事件响应的方式唤醒处理线程。效率较select高且无最大待处理socket数量限制。



用户头像

2流程序员

关注

还未添加个人签名 2020.03.18 加入

还未添加个人简介

评论

发布
暂无评论
数据结构与算法、网络模型总结