时间复杂度
image.png
image.png
由上图，可见，O(1) 最小，O(logn) 次之，比如二分查找就是 O(logn) 时间复杂度
可见 二分查找，除了hash外，相比 其他数据结构的查找，还是很快的
比如 红黑树，二叉查找数，二叉平衡树，因为查找时正好都是从根开始，要么左查，要么右查，正好也是二分查找，所以查找的时间复杂度也是 O(logn)
O(logn) 的计算 ：
时间复杂度的计算实际上就是代码执行的最多的次数。
具体执行的次数，可以通过一个多项式表示出来，比如 n^3+n^2+n，然后取影响最大的一项，即 n^3，所以，时间复杂度就是 O(n^3)
再看 O(logn) 的计算，以二分法来看，看代码执行的次数：
对于 n长的排完序的数组，
第一次查找，排除 n/2 的数据
第二次查找，排除 剩下的 n/2 的一半的数据，n/2/2 -> n/2^2
第三次查找，同样，取上次剩下的一半，n/2/2/2 -> n/2^3
...
第m次查找， 找到了，此时剩下了唯一的一个数据，也就是
m次查找后剩下的数据是: n/2^m
因为剩下的是唯一一个数据，所以，n/2^m = 1
即
n = 2^m
logn = m
所以，m 的值是 logn
空间复杂度
主要衡量 算法锁占用的内存空间
需要使用多少的临时内存来处理数据，和 原始数据 n 的数量有多少关系
比如，如果需要拷贝一份原始数据，则空间复杂度为 O(n)
如果和原始数据n个数无关，则空间负载度为 O(1)
同样，如果说要拷贝两份数据才能完成，则空间复杂度为 O(n^2)
数据结构
队列，栈
链表
数 - 二叉树，n叉树，二叉查找树，红黑树
堆
Hash
跳跃表
算法
穷举, 递归
贪心算法
分治算法
动态规划
网络通信协议，主要关注 4 层协议模型
image.png
其中需要对每一层的协议的大致格式，数据传输，都需要有一定了解
特别是 tcp 的握手挥手，通信中的 seq/ack , tcp状态转移图， http 的协议格式，需要有更深入的了解
阻塞IO，非阻塞IO
针对 IO操作的阻塞非阻塞，指定的是IO操作未完成时，会不会立即返回。
非阻塞IO，当读或者写IO时，如果操作不成功(没数据可读，没空间可写)，会立即返回
而阻塞IO，会等待直到操作成功才会返回
阻塞非阻塞IO 和 同步异步没有任何关系，
因为一个文件操作符，比如socket，你可以设置为阻塞的，也可以设置为非阻塞的，
而同步异步操作，只是你的行为,
你愿意等上一个操作完，然后进行下一步操作，就是同步的，
你不愿意等上一个操作完成，只是发了个信号，启动上一个操作，就去做下一步操作，然后上一步操作完成后，通知你，就是异步的
个人理解，阻塞非阻塞是一个事物的特性，比如socket
同步异步，是你如果去操作这个事物的行为，比如等读完成，或者发个读信号，读完之后，会通知我
目前linux 异步IO AIO 应用还不太广泛，所以，基本上还是同步阻塞，同步非阻塞 以及 I/O 复用几种方式
I/O 复用
有 select/poll epoll 几种方式
目前主要使用 epoll 的方式
select/poll 每次通知有事件时，需要遍历已注册的所有的事件，查询每个事件的状态，看是否可读写
epoll 直接返回的就是可读写的事件，只需要循环处理这些事件即可
网友评论