HTTP协议

HTTP 协议的请求报文和响应报文的结构基本相同,主要由三大部分组成:

  • 状态行(status line):描述响应的基本信息,也就是服务器响应的状态;
  • 头部字段集合(header):使用 key-value 形式更详细地说明报文;
  • 消息正文(entity):实际响应的数据,它不一定是纯文本,可以是图片、视频等二进制数据。
Read More

HTTPS

工作流程

  1. Client发起一个HTTPS(比如 https://juejin.im/user )的请求,根据RFC2818的规定,Client知道需要连接Server的443(默认)端口。
  2. Server把事先配置好的公钥证书(public key certificate)返回给客户端。
  3. Client验证公钥证书:比如是否在有效期内,证书的用途是不是匹配Client请求的站点,是不是在CRL吊销列表里面,它的上一级证书是否有效,这是一个递归的过程,
    直到验证到根证书(操作系统内置的Root证书或者Client内置的Root证书)。如果验证通过则继续,不通过则显示警告信息。
Read More

复杂度定义

时间复杂度

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),进而分析f(n)随n的变 化情况并确定T(n)的数量级。这里用”O”来表示数量级,
给出算法的时间复杂度。

T(n)=O(f(n));

它表示随着问题规模的n的增大,算法的执行时间的增长率和f(n)的增长率相同,这称作算法的渐进时间复杂度,简称时间复杂度。

Read More

查找算法

顺序查找

顺序查找(Sequential Search)又称线性查找。从表中第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定值相等,则查找成功,如果查找到表中最后一个元素,还没有找到,则查找不成功。

二分查找

二分查找(Binary Search)又称折半查找。它的前提是线性表中的记录必须是关键码有序,线性表必须采用顺序存储。折半查找的基本思想是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止。

基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。即根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式mid=low+(key-a[low])/(a[high]-a[low])(high-low),替换了二分查找的计算公式mid=low+1/2(high-low)。

这样的好处在于,对表长较长,且关键字分布比较均匀,插值查找算法的平均性能要比折半查找要好的多。但是如果表中关键字分布极端不均匀,那么插值查找还不如折半查找呢。

也是一种改进的二分查找,通过运用黄金比例的概念在数列中选择查找点进行查找,提高查找效率。

Read More