week08 小结

时间复杂度与空间复杂度



时间复杂度

• 并不是计算程序具体运行的时间，而是算法执行语句的次数。

• O(2^n)表示对n数据处理需要进行2^n次计算

• O(1)，O(log(n))，O(n^a) 多项式时间复杂度

• O(a^n) 和O(n!) 非多项式时间复杂度

空间复杂度

• 一个算法在运行过程中临时占用存储空间大小的量度。

• O(n) 表示需要临时存储n个数据



NP问题

P：能在多项式时间复杂度内解决的问题

NP：能在多项式时间复杂度内验证答案正确与否的问题。



常见数据类型：数组、链表、HASH、栈、队列、树



树：二叉树、二叉排序树、平衡二叉树、红黑树、跳表



常见算法：穷举算法、递归算法、贪心算法、动态算法、遗传算法



OSI七层模型和TCP/IP四层模型

OSI七层模型：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层

TCP/IP四层模型：应用层、传输层、网络互联层、网络访问（链路）层



网络数据包格式：HTTP协议头 -> TCP协议头 ->IP协议头 ->链路层协议头



http协议有1.0、 1.1 、 2