初赛干货

排序

稳定排序：冒泡排序、插入排序、归并排序、基数排序

不稳定排序：选择排序、快速排序、希尔排序、堆排序

稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序

• 冒泡排序

  每次找相邻的元素，如果左边比右边大，就交换，这样保证每次扫下来当前待排序的列最后一个元素是当前列中最大的元素，这样就不用管它了，把它踢掉，对剩下的继续上述扫描直到没有为止。

  因为如果两个相邻元素相同，是不会交换的；如果两个相等元素没有相邻，即使通过交换能让两个元素相邻，也不会交换，所以相同元素前后顺序不变，是稳定的。

  最好时间复杂度： Θ ( n ) \Theta(n) Θ(n)，最坏时间复杂度： Θ ( n 2 ) \Theta(n^2) Θ(n2)。

• 选择排序

  每次从待排序的序列中找到最小（最大）的元素放在开头，再从剩下的元素中找到最小（最大）放在已排好序的末尾，知道待排序列没有元素为止。

  在一趟选择，如果一个元素比当前元素小，而小的元素又出现在和当前元素相等的元素的后面，稳定性就被破坏了。比如 5   8   5   2   9 5\ 8\ 5\ 2\ 9 5 8 5 2 9，第一遍选择 5 5 5 和 2 2 2 会交换，于是原序列中 5 5 5 的相对前后顺序就破坏了，它是不稳定的。

  比较次数 Θ ( n 2 ) \Theta(n^2) Θ(n2) ，与元素初始状态无关，总比较次数 N = ( n − 1 ) + ( n − 2 ) + ⋯ + 1 = n ∗ ( n − 1 ) 2 N=(n-1)+(n-2)+\dots+1=\frac{n*(n-1)}2 N=(n−1)+(n−2)+⋯+1=2n∗(n−1)​ ；交换次数 Θ ( n ) \Theta(n) Θ(n)，最好情况 0 0 0 次（有序），最坏交换 n − 1 n-1 n−1 次，逆序交换 n 2 ​ \frac n 2​ 2n​​ 。

• 插入排序

  从有序数列和无序数列开始，每次从无序数列弹出一个数，在有序数列中依次比较，找到一个合适的位置插入。

  显然，这个算法具有稳定性。

  时间复杂度： Θ ( n 2 ) \Theta(n^2) Θ(n2)。

• 快速排序

  设定一个分界值，让左边的元素不大于分界值，右边元素不小于分界值，然后左右依次递归下去。至于实现：

  1）设置两个变量 i , j i,j i,j ，排序开始的时候： i = 0 i=0 i=0 ， j = N j=N j=N ；

  2）以第一个数组元素作为关键数据，赋值给key，即 key = A [ 0 ] ​ =A[0]​ =A[0]​ ；

  3）从 j j j 开始向前搜索，即由后开始向前搜索(j–) ，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；

  4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；

  5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

  演示：

  假设一开始序列 { x i } \{x_i\} {xi​} 是： 5 ， 3 ， 7 ， 6 ， 4 ， 1 ， 0 ， 2 ， 9 ， 10 ， 8 5，3，7，6，4，1，0，2，9，10，8 5，3，7，6，4，1，0，2，9，10，8 。

  此时， r e f = 5 ref=5 ref=5， i = 1 i=1 i=1， j = 11 j=11 j=11，从后往前找，第一个比 5 5 5 小的数是 x 8 = 2 x_8=2 x8​=2 ，因此序列为： 2 ， 3 ， 7 ， 6 ， 4 ， 1 ， 0 ， 5 ， 9 ， 10 ， 8 2，3，7，6，4，1，0，5，9，10，8 2，3，7，6，4，1，0，5，9，10，8 。此时 i = 1 i=1 i=1 ， j = 8 j=8 j=8 ，从前往后找，第一个比 5 5 5 大的数是 x 3 = 7 x_3=7 x3​=7 ，因此序列为： 2 ， 3 ， 5 ， 6 ， 4 ， 1 ， 0 ， 7 ， 9 ， 10 ， 8 2，3，5，6，4，1，0，7，9，10，8 2，3，5，6，4，1，0，7，9，10，8 。此时， i = 3 i=3 i=3 ， j = 8 j=8 j=8 ，从第 8 8 8 位往前找，第一个比 5 5 5 小的数是 x 7 = 0 x_7=0 x7​=0 ，因此： 2 ， 3 ， 0 ， 6 ， 4 ， 1 ， 5 ， 7 ， 9 ， 10 ， 8 2，3，0，6，4，1，5，7，9，10，8 2，3，0，6，4，1，5，7，9，10，8 。此时，$ i=3$ ， j = 7 j=7 j=7 ，从第 3 3 3 位往后找，第一个比 5 5 5 大的数是 x 4 = 6 x_4=6 x4​=6 ，因此： 2 ， 3 ， 0 ， 5 ， 4 ， 1 ， 6 ， 7 ， 9 ， 10 ， 8 2，3，0，5，4，1，6，7，9，10，8 2，3，0，5，4，1，6，7，9，10，8 。此时， i = 4 i=4 i=4 ， j = 7 j=7 j=7 ，从第 7 7 7 位往前找，第一个比 5 5 5 小的数是 x 6 = 1 x_6=1 x6​=1 ，因此： 2 ， 3 ， 0 ， 1 ， 4 ， 5 ， 6 ， 7 ， 9 ， 10 ， 8 2，3，0，1，4，5，6，7，9，10，8 2，3，0，1，4，5，6，7，9，10，8 。此时， i = 4 i=4 i=4 ， j = 6 j=6 j=6 ，从第 4 4 4 位往后找，直到第 6 6 6 位才有比 5 5 5 大的数，这时， i = j = 6 i=j=6 i=j=6 ， r e f ref ref 成为一条分界线，它之前的数都比它小，之后的数都比它大，对于前后两部分数，可以采用同样的方法来排序。

  显然，多个相同的值的相对位置可能会在算法结束是产生变动，因此它是不稳定的。

  一趟的时间复杂度为 Θ ( n ) \Theta(n) Θ(n) ，而总的与划分趟数相关。理想状况就是每次划分所选的值恰好将序列几乎等分，这样总时间复杂度： Θ ( n log ⁡ n ) \Theta(n\log n) Θ(nlogn) 。最坏的情况是每次所选的值恰好是当前序列的最大（最小）值，这样有一边就是空的，时间复杂度： Θ ( n 2 ) \Theta(n^2) Θ(n2) 。

  于是我们可以对选分界值进行优化：

  1、三数取中法：找到数组中最小下标，最大下标，中间下标的数字，进行比较，把中间大的数组放在最左边；

  2、随机选取分界值

• 归并排序

  这个很清楚，就不再赘述。

  在合并过程中我们可以保证当两个元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，因此它是稳定的。

  时间复杂度： Θ ( n log ⁡ n ) \Theta(n\log n) Θ(nlogn) 。

• 基数排序

  按个位的数值在扫描时分别将其分配至 0 0 0 到 9 9 9 的桶中，然后再到十位、百位……

  由于它基于分别排序，分别收集，所以它是稳定的。

  时间复杂度： Θ ( d ( n + k ) ) \Theta(d(n+k)) Θ(d(n+k)) ，其中 n n n 表示待排序列的规模，而 k k k 表示每一位数的范围， d d d 表示待排序列的最大位数。

• 希尔排序

  先取一个小于 n n n 的整数 d 1 d_1 d1​ ，把所有序号相隔 d 1 d_1 d1​ 的元素放在一组，组内直接进行插入排序；然后取 d 2 < d 1 d_2<d_1 d2​<d1​ ，重复上述分组和排序操作；直至 d i = 1 d_i=1 di​=1 ，即所有记录都放进了一个组，排序结束。

  由于多次插入排序，在不同插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。

  时间复杂度： Θ ( n 1.3 ) \Theta(n^{1.3}) Θ(n1.3) ，下界为 Θ ( n 2 ) \Theta(n^2) Θ(n2) 。

• 堆排序

  利用堆这种数据结构实现的排序。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：子节点的键值或索引总是小于（大于）其父节点。

  现有以下几种操作：

  • 最大堆调整：将堆末端子节点作调整，使得子节点永远小于父节点
  • 创建最大堆：将堆中所有数据重新排序
  • 堆排序：弹出位在第一个数据的根节点，并做最大堆调整的递归运算，这样就不断弹出最大值，完成排序
  时间复杂度： Θ ( n log ⁡ n ) \Theta(n\log n) Θ(nlogn) 。

总结：

主定理 ( M a s t e r Master Master)

转自 Chanis的博客

• 时间复杂度

  一个程序的语句执行次数可以用一个代数式表示，那么就取这个代数式的最高次项且忽略此项系数作为时间复杂度。

T ( n ) T(n) T(n) 表示时间复杂度，我们可以这么表示：

T ( n ) = T(n)= T(n)= 下面任意一个符号 ( ( (一个单项式 ) ) )。

Θ \Theta Θ ，等于。

O O O ，小于等于。

o o o ，小于。

Ω \Omega Ω ，大于等于。

ω \omega ω ，大于。

• 主定理

  我们将一个规模为 n n n 的问题，通过分治得到 a a a 个规模为 n b \frac n b bn​ 的子问题，每次递归带来的额外计算为 f ( n ) f(n) f(n) ，于是我们可以得到以下关系式：

  T ( n ) = a T ( n b ) + f ( n ) T(n)=aT(\frac n b)+f(n) T(n)=aT(bn​)+f(n)

  另外，定义一个 c c r i t c_{crit} ccrit​ ，它的值为：

  c c r i t = log ⁡ b a c_{crit}=\log_ba ccrit​=logb​a

  有三种情况:

  1、当 f ( n ) = O ( n c ) f(n)=O(n^c) f(n)=O(nc) ，且 c < c c r i t c<c_{crit} c<ccrit​ 时

  T ( n ) = Θ ( n c c r i t ) T(n)=\Theta(n^{c_{crit}}) T(n)=Θ(nccrit​)

  2、当 f ( n ) = Θ ( n c c r i t log ⁡ k n ) f(n)=\Theta(n^{c_{crit}}\log^kn) f(n)=Θ(nccrit​logkn) ，且 k ≥ 0 k\ge0 k≥0 时

  T ( n ) = Θ ( n c c r i t log ⁡ k + 1 n ) T(n)=\Theta(n^{c_{crit}}\log^{k+1}n) T(n)=Θ(nccrit​logk+1n)

  3、当 f ( n ) = Ω ( n c ) f(n)=\Omega(n^c) f(n)=Ω(nc) ，且 c > c c r i t c>c_{crit} c>ccrit​ 时

  T ( n ) = Θ ( f ( n ) ) T(n)=\Theta(f(n)) T(n)=Θ(f(n))

  其中第二条还有三个扩展（前提当然都满足等式）：

  1） k > − 1 k>-1 k>−1 时

  T ( n ) = Θ ( n c c r i t log ⁡ k + 1 n ) T(n)=\Theta(n^{c_{crit}}\log^{k+1}n) T(n)=Θ(nccrit​logk+1n)

  2） k = − 1 k=-1 k=−1 时

  T ( n ) = Θ ( n c c r i t log ⁡ log ⁡ n ) T(n)=\Theta(n^{c_{crit}}\log\log n) T(n)=Θ(nccrit​loglogn)

  3） k < − 1 k<-1 k<−1 时

  T ( n ) = Θ ( n c c r i t ) T(n)=\Theta(n^{c_{crit}}) T(n)=Θ(nccrit​)

  不过这三条很少用。

编译性和解释性语言

编译性语言

程序在执行之前需要一个专门的编译过程，把程序编译成为机器语言的文件，运行时不需要重新翻译，直接使用编译结果就行了。

• C C C++
• C C C
• D e l p h i Delphi Delphi

解释性语言

用解释性语言编写的程序不进行预先编译，以文本方式存储程序代码。在发布程序时，看起来省了道编译工序，但是，在运行程序的时候，解释性语言必须 先解释再运行 。

• J a v a Java Java
• J a v a S c r i p t JavaScript JavaScript
• V B S c r i p t VBScript VBScript
• P e r l Perl Perl
• P y t h o n Python Python
• R u b y Ruby Ruby
• M A T L A B MATLAB MATLAB

P、NP、NPC、NP-Hard问题

转自这里

P 类问题

P 指 P o l y n o m i n a l Polynominal Polynominal ，多项式。

所以 P 类问题就是存在 多项式时间算法 的问题。

比如排序问题，在其中可以找到时间复杂度为多项式 Θ ( N 2 ) \Theta(N^2) Θ(N2) 的算法（冒泡等），所以说排序就是个 P 类问题。

NP 类问题

NP 指 N o n d e t e r m i n i s t i c   P o l y n o m i n a l Nondeterministic\ Polynominal Nondeterministic Polynominal ，非确定性多项式。

所以 NP 类问题就是能在多项式时间内验证得出一个正确解的问题。

P 类问题是它的子集，因为存在多项式时间解法的问题，总能在多项式时间内验证它。

最为著名的就是 旅行家推销问题 ( TSP ) ：

即有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的环路，这个环路路径小于a。我们知道如果单纯枚举会有(n-1)! 种，这已不是多项式时间的算法了，(注：阶乘算法比多项式的复杂)。

但是，我们可以猜，假设猜几次就猜中了一条小于长度a的路径，问题解决了。可是，我们不可能每次都猜的那么准，也许我们要猜完所有情况呢？所以说这是一个 NP 类问题。也就是，我们能在多项式的时间内验证并得出问题的正确解，可是我们却不知道该问题是否存在一个多项式时间的算法，每次都能解决他(注意，这里是不知道，不是不存在)。

NPC 类问题

NP-Complete ，规约。

这是 NP 类问题的一个子集，且其中每一个问题均能由 NP 中的任何问题在多项式时间内转化成。

很多时候 NPC 问题是找不到一个多项式时间算法的，更多时候它是一个指数级的算法。

这类问题满足两个性质，一个就是在多项式时间内可以验证一个解是不是正确的解，另一个性质就是可以把任何一个 NP 问题在多项式的时间内把它的输入转化，使之为 NPC 类问题。 NPC 类问题在多项式时间内可以互相转换，只要其中一个问题可以在多项式时间内解决，那么其它问题也都将可以在多项式时间内解决。

NPH 类问题

NP-Hard 。

若问题A不属于NP类，已知某一NPC问题可在多项式时间内转化为问题A，则称A为NPH。

面向对象语言

典型：

• s i m u l a   67 simula\ 67 simula 67
• S m a l l t a l k Smalltalk Smalltalk
• E I F F E L EIFFEL EIFFEL
• C C C++
• J a v a Java Java
• C C C#
• O b j e c t i v e − C Objective-C Objective−C
• P H P PHP PHP
• P y t h o n Python Python
• g o go go
• V B . n e t VB.net VB.net
• V B   6.0 VB\ 6.0 VB 6.0
• 易语言
• O b j e c t i v e   P a s c a l Objective\ Pascal Objective Pascal ( 现已改称为 D e l p h i Delphi Delphi )

特点：

• 基础：
  • 识认性：系统中的基本构件可识认为一组可识别的离散对象
  • 类别性：系统具有相同数据结构与行为的所有对象可组成一类
  • 多态性：对象具有唯一的静态类型和多个可能的动态类型
• 特色：
  • 继承性：在基本层次关系的不同类中共享数据和操作
  有时候还会加上动态绑定

补码、反码、原码

• int变量的储存方式

  类型名称	占字节数	取值范围
  i n t int int	4 B 4B 4B	− 2 31 ∼ 2 31 − 1 -2^{31}\sim2^{31}-1 −231∼231−1
  u n s i g n e d   i n t unsigned\ int unsigned int	4 B 4B 4B	0 ∼ 2 32 0\sim2^{32} 0∼232

  i n t int int 有正负号比 u n s i g n e d   i n t unsigned\ int unsigned int 多消耗一位来记录符号，其最高位为符号位， 0 0 0 为正数， 1 1 1 为负数，因此你会发现多了一个 - 0 0 0 ，于是特别地将它定义为 − 2 31 -2^{31} −231 ，这也是为什么正数最高要减一。

• 原码

  它是一种对数字的二进制定点表示方法。原码表示法在最高位有一位符号位， 0 0 0 为正数， 1 1 1 为负数，就是上面这种方式。但我们在内存中不用原码表示数值，因为它作为代码加减运算时较为复杂，所以一般不采用这种编码。

• 反码

  正数和"+0"的反码与原码相同，负数反码除符号位相同，其他位全部取反。

  但是由于 - 0 0 0 的存在，使得二进制和十进制的互换不能一一对应，这样会使得计算机要增加额外的物理硬件配合运算，所以，这种方法也被很早就抛弃了。

• 补码

  正数和"+0"的补码与原码相同，负数先计算其反码，再在反码上加 1 得到补码。

  我们知道 8 8 8 位二进制的符号数的取值范围是 − 2 7 ∼ 2 7 − 1 -2^7\sim2^7-1 −27∼27−1 ，即 − 128 ∼ 127 -128\sim127 −128∼127 。

  于是我们看一下 ( − 1 ) + ( − 127 ) = − 128 (-1)+(-127)=-128 (−1)+(−127)=−128 的加法：

  十进制	原码	反码	补码
  -1	1000 0001	1111 1110	1111 1111
  -127	1111 1111	1000 0000	1000 0001
  结果（补码）	1000 0000
  结果（反码）
  结果（原码）
  结果（十进制）	-128

  由于补码 1000   0000 1000\ 0000 1000 0000 具有特殊性，于是将其规定为 − 128 -128 −128 ，其值恰好符合 (-1)+(-127) 的结果；且 8 8 8 位二进制补码 1000   0000 1000\ 0000 1000 0000 没有对应的反码和原码，其他位数的二进制补码类似。

网络基础

网络

定义

计算机网络是由地理位置分散的、具有独立功能的多个计算机系统，经通讯设备和线路互相连接，并配以相应的网络软件，以实现通信和资源共享的系统。

功能

• 信息交换
• 资源共享
• 分布式处理

网络的拓扑结构

• 总线拓扑

  这是一种共享通路的物理结构，它的总线具有信息的双向传输功能，普遍用于局域网的连接，一般采用同轴电缆或双绞线。

  优点：安装容易，节点故障不会殃及系统，信道利用率高。

  缺点：由于信道共享，连接的节点不宜过多，且总线自身故障会导致系统崩溃。

• 星型拓扑

  这是一种以中央节点为中心，把若干外围节点连接起来的辐射式互联结构，它适用于局域网，通常以集线器作为中央节点，并且以同轴电缆或双绞线作为连接线路。

  优点：安装容易、结构简单、费用低。

  缺点：中央节点的正常运行对网络系统至关重要。

• 环形拓扑

  它是将网络节点连接成闭合结构，信号顺着一个方向从一台设备传到另一台设备，每一台设备都配有一个收发器，信息在每台设备上的延时时间是固定的。它适用于实时控制的局域网系统。

  优点：安装容易、费用较低、电缆故障容易查找和排除。

  缺点：当节点发生故障时，整个网络就不能正常工作。

• 树形拓扑

  它就像一颗“根”朝上的树，适用于军事单位、政府部门等上下界限相当严格和层次分明的部门，一般采用同轴电缆。

  优点：容易扩展、故障也容易分离处理。

  缺点：整个网络对根的依赖性很大，一旦网络的根发生故障，整个系统就不能正常工作。

• 网状拓扑

  它主要指各节点通过传输线互联连接起来，并且每一个节点至少与其他两个节点相连，然而，它并不常用于局域网。

  优点：较高的可靠性。

  缺点：结构复杂、费用较高、不易管理和维护。

• 混合拓扑

  它是将两种或几种网络拓扑结构混合起来构成的一种网络拓扑结构，这种结构是由星型结构和总线型结构的网络结合在一起的，这样的拓扑结构更能满足较大网络的拓展，解决星型网络在传输距离上的局限，同时又解决了总线型网络在连接用户数量的限制，它同时兼顾两者的优点，并在缺点方面得到了一定的补充。

• 蜂窝拓扑

  它是无限局域网中常用的结构。它以无限传输介质（微博、卫星、红外等）点到点和多点传输为特征，是一种无线网，适用于城市网、校园网、企业网。

计算机网络系统

1、硬件系统

• 服务器

  一台速度快，存储量大的计算机，它是网络系统的核心设备，负责网络资源管理和用户服务。

• 工作站

  具有独立处理能力的计算机，是用户向服务器申请服务的终端设备。

• 网卡

  又称网络适配器，是计算机和计算机之间直接或间接传输介质互相通信的接口，它插在计算机的扩展槽中。它将计算机的数字信号转换成通信线路能够传送的电子信号或电磁信号。

• 调制解调器

  一种信号转换装置，它的作用是将计算机与公用电话线相连。

  

• 集线器

  局域网中的连接设备，有多个端口，可连接多台计算机。

• 交换机

  集线器是工作在带宽共享方式下的，多台计算机通过各个端口连接到集线器上时，它们只能共享一个信道的带宽；交换机则是模拟用网桥连接各个网络的方式工作。

• 网桥

  局域网使用的连接设备，它的作用是扩展网络的距离，减轻网络的负载。当信号通过时，它会将非本网段的信号排除掉，使网络信号能更有效使用信道，从而减轻网络负担。

• 路由器

  互联网中的连接设备，可以将两个网络连接在一起组成更大的网络，它不仅有网桥的全部功能，还具有路径的选择功能。

• 网关

  一种复杂的网络连接设备，它工作在 O S I OSI OSI 高三层，用来连接异构网络，具有对不兼容的高层协议进行转换的功能 。

2、软件系统

• 数据通信软件

  按网络协议要求完成通信功能的软件。

• 网络操作系统

  能够控制和管理网络资源的软件。

  它的功能作用在两个级别上：

  • 服务器机器

    为在服务器上的任务提供资源管理

  • 工作站机器

    向用户和应用软件提供一个网络环境的“窗口”

  常见的有： W i n d o w s 、 U n i x 、 L i n u x Windows、Unix、Linux Windows、Unix、Linux 等。

• 网络应用软件

  网络能够为用户提供各种服务的软件。

3、网络信息系统

以计算机网络为基础开发的信息系统。

网络的分类

1、按地理范围分类

• 局域网 LAN

  一般在几百米到 10km 之内，属于小范围的连网，如建筑物内、学校等。

• 城域网 MAN

  一般在几十公里到上百公里，是一种中等形式的网络，如城市、地区。

• 广域网 WAN

  一般在几千公里左右，属于大范围连网，是网络系统中最大型的网络，能实现大范围内的资源共享，如 I n t e r n e t Internet Internet 。

2、按传输速率分类

• 低速网

  一般传输速率在 K b / s ∼ M b / s Kb/s\sim Mb/s Kb/s∼Mb/s 范围内

• 高速网

  一般传输速率在 M b / s ∼ G b / s Mb/s\sim Gb/s Mb/s∼Gb/s 范围内

有时也将 K b / s Kb/s Kb/s 的网称为低速网， M b / s Mb/s Mb/s 的网称为中速网， G b / s Gb/s Gb/s 的网称为高速网。

网络的传输速率与它的带宽有直接关系。带宽是指传输信道的宽度，其单位是 H z Hz Hz（赫兹）。

• 窄带网

  K H z ∼ M H z KHz\sim MHz KHz∼MHz 带宽的网络

• 宽带网

  M H z ∼ G H z MHz\sim GHz MHz∼GHz 带宽的网络

有时也将 K H z KHz KHz 带宽的网称为窄带网，将 M H z MHz MHz 带宽的网称为中带网，将 G H z GHz GHz 带宽的网称为宽带网。

通常情况下，高速网就是宽带网，低速网就是窄带网。

3、按传输介质分类

• 传输介质

  数据传输系统中发送装置和接受装置间的物理媒体

• 有线网

  传输介质采用有线介质连接的网络。常用的有线传输介质有双绞线、同轴电缆和光导纤维。

• 无线网

  采用无线介质连接的网络。包括通过移动通信网实现的无线网络（如 4 G 4G 4G、 3 G 3G 3G 或 G P R S GPRS GPRS）、无线局域网（ W i F i WiFi WiFi）、微波、红外线、激光等方式。

O S I OSI OSI 模型

来由

在同一网络系统中网络协议是一致的，节点间通信方便，但在不同网络系统中网络协议很可能不一致，造成不便。于是国际标准化组织 I S O ISO ISO 于 1981 1981 1981 年推出 O S I OSI OSI（开放系统互联结构模型）。

目标

所有网络系统都向此标准靠拢，消除不同系统之间因协议不同而造成的通信障碍，使得不同网络系统在互联网范围内不要专门的转化装置就能进行通信。

功能

它是一个将网络协议规范化了的逻辑参考模型。它根据网络系统的逻辑功能将其分为七层，并对每一层规定了功能、要求、技术特性等，但没规定具体的实现方法。它仅仅是一个标准而不是特定的系统或协议。

结构

O S I OSI OSI 把计算机网络分为通信子网和资源子网两大部分。

• 通信子网

  O S I OSI OSI 参考模型低三层：物理层、数据链路层和网络层

• 资源子网

  O S I OSI OSI 参考模型高三层：会话层、表示层和应用层

• 传输层

  起着承上启下的作用

I n t e r n e t Internet Internet

国际计算机互联网的简称，是世界上规模最大的计算机网络。从 1994 1994 1994 年 4 4 4 月起，我国正式加入 I n t e r n e t Internet Internet ，并在 1997 1997 1997 年 4 4 4 月 26 26 26 日使 C S T n e t \mathrm{CSTnet} CSTnet（科技网）、 C E R n e t \mathrm{CERnet} CERnet（教育科研网）、 C H I N A n e t \mathrm{CHINAnet} CHINAnet（中国互联网）、 C h i n a G B N \mathrm{ChinaGBN} ChinaGBN（ G o l d   B r i g d e \mathrm{Gold\ Brigde} Gold Brigde 金桥网）相互连通。

浏览器

可以显示网页服务器或者文件系统的 H T M L HTML HTML 文件（标准通用标记语言的一个应用）内容，并让用户与这些文件交互的一种软件，大部分为 H T M L HTML HTML 格式。

一个网页中可以包含多个文档，每个文档都是分别从服务器获取的。

常见的有：百度、 G o o g l e   C h r o m e Google\ Chrome Google Chrome 等。

网络协议

在计算机网络中一系列的通信规则和约定的集合。

TCP/IP

传输控制协议 ( T r a n s m i s s i o n   C o n t r o l   P r o t o c o l Transmission\ Control\ Protocol Transmission Control Protocol )/因特网互联协议 ( I n t e r n e t   P r o t o c o l Internet\ Protocol Internet Protocol )，又叫网络通讯协议。TCP/IP 协议把 I n t e r n e t Internet Internet 网络系统描述成具有四个层次功能的网络模型，包括：链路层、网络层、传输层和应用层。

• 链路层

  该结构的第一层，也叫网络接口层，其功能是提供网络相邻节点间的信息传输以及网络硬件的设备驱动。

• 网络层

  I P IP IP 协议层，其功能是提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能。

• 传输层

  提供网络上各应用程序之间的通信服务。

• 应用层

  该结构最高层，其功能是为用户提供访问网络环境的手段，主要提供 F T P FTP FTP、 T E L N E T TELNET TELNET 等功能软件。

IP 协议适用于所有类型网络。TCP 协议则处理 IP 协议所遗留的通信问题，为应用程序提供可靠的通信连接，并能自动适应网络的变化。TCP/IP 目前已成为最成功的网络体系结构和协议规范。

常见的应用层协议包括：超文本传输协议（HTTP）、文本传输协议（FTP）、远程登录协议（Telnet）、简单邮件传输协议（SMTP：发送电子邮件，POP3：接受电子邮件）等。

IP 地址

通常一个 IP 地址共有 32 32 32 位，分为 4 4 4 段，每段 8 8 8 位（即 1 1 1 个字节），每段的取值范围 0 ∼ 255 0\sim255 0∼255，其中 IPv6 有 128 128 128 位。IP 地址是 Internet 上主机的一种数字标识，它由两部分组成，一部分是网络标识，另一部分是主机标识。

• A 类网（大型网络）

  第一段取值在 1 ∼ 127 1\sim127 1∼127 之间，其值就是网络的网络号，后三段表示该主机号。

• B 类网（中型网络）

  第一段取值在 128 ∼ 191 128\sim191 128∼191 之间，第一段和第二段的数字联合表示该网络的网络号，第三段则表示子网号，第四段则是该主机号。

• C 类网（小型网络）

  第一段取值在 192 ∼ 223 192\sim223 192∼223 的，第一、二、三段数字组合表示该网络的网络号，第四段是主机号。

这三类地址的特征为

• A 类网以 0 0 0 开头，网络号码是 8 8 8 位，主机号码是 24 24 24 位
• B 类网以 10 10 10 开头，网络号码是 16 16 16 位，主机号码是 16 16 16 位
• C 类网以 110 110 110 开头，网络号码是 24 24 24 位，主机号码是 8 8 8 位

另：

• D 类网以 1110 1110 1110 开头
• E 类网以 11110 11110 11110 开头

私有 IP 地址

以下为 A、B、C 类网络中的私有地址段：

• 10.0.0.0 ∼ 10.255.255.255 10.0.0.0\sim10.255.255.255 10.0.0.0∼10.255.255.255
• 172.16.0.0 ∼ 172.131.255.255 172.16.0.0\sim172.131.255.255 172.16.0.0∼172.131.255.255
• 192.168.0.0 ∼ 192.168.255.255 192.168.0.0\sim192.168.255.255 192.168.0.0∼192.168.255.255

子网掩码

它的作用就是和 IP 地址 “ & \And &” 后得出网络地址，子网掩码也是 32 32 32 位，并且是一串 1 1 1 后跟随一串 0 0 0 组成，其中 1 1 1 表示在 IP 地址中的网络号对应的位数，而 0 0 0 表示在 IP 地址中主机对应的位数。

例如 11111111   11111111   11111111   00000000 11111111\ 11111111\ 11111111\ 00000000 11111111 11111111 11111111 00000000 中，前三个字节全是 1 1 1 ，代表对应 IP 地址中最高的三个字节为网络地址；后一个字节全是 0 0 0 ，代表对应 IP 地址中最后一个字节为主机地址。

缺省子网掩码

A 类网络的缺省子网掩码为 255.0.0.0 255.0.0.0 255.0.0.0

换算成二进制为 11111111.00000000.00000000.00000000 11111111.00000000.00000000.00000000 11111111.00000000.00000000.00000000，可以清楚的看出前 8 8 8 位是网络地址，后 24 24 24 位是主机地址，也就是说，如果采用的是标准的子网掩码，看第一段地址即可看出是不是同一网络的。如 21.0.0.1 21.0.0.1 21.0.0.1 和 21.240.230.1 21.240.230.1 21.240.230.1 ，第一段为 21 21 21 属于 A 类，如果用的是默认子网掩码，那这两个地址就是一个网段的。

B 类网络的缺省子网掩码为 255.255.0.0 255.255.0.0 255.255.0.0

C 类网络的缺省子网掩码为 255.255.255.0 255.255.255.0 255.255.255.0

确定网络号和主机号

子网掩码与 IP 地址子网掩码与 IP 地址结合使用，可以区分出一个网络地址的网络号和主机号。例如有一个 C 类地址为 192.9.200.13 192.9.200.13 192.9.200.13，其子网掩码为 255.255.255.0 255.255.255.0 255.255.255.0 ，则它的网络号和主机号可按如下方法得到：

1、将 IP 地址 192.9.200.13 192.9.200.13 192.9.200.13 转换成二进制： 11000000   00001001   11001000   00001101 11000000\ 00001001\ 11001000\ 00001101 11000000 00001001 11001000 00001101

2、将子网掩码 255.255.255.0 255.255.255.0 255.255.255.0 转化成二进制： 11111111   11111111   11111111   00000000 11111111\ 11111111\ 11111111\ 00000000 11111111 11111111 11111111 00000000

3、将两个二进制数 “ & \And &” 后得出结果 11000000   00001001   11001000   00000000 11000000\ 00001001\ 11001000\ 00000000 11000000 00001001 11001000 00000000 转换成十进制，即为网络号 192.9.200.0 192.9.200.0 192.9.200.0

4、将子网掩码取反再与 IP 地址 “ & \And &” 后得到结果 00000000   00000000   00000000   00001101 00000000\ 00000000\ 00000000\ 00001101 00000000 00000000 00000000 00001101 转换成十进制，即为主机号 13 13 13

基础算法

位运算

二进制状态压缩

我们默认一个长度为 m m m 的二进制数是从 0 ∼ m − 1 0\sim m-1 0∼m−1 位。

操作	运算
取出整数 n n n 在二进制表示下的第 k k k 位	(n >> k) & 1
取出整数 n n n 在二进制表示下的第 0 ∼ k − 1 0\sim k-1 0∼k−1 位	n & ( (1 << k) - 1 )
把整数 n n n 在二进制表示下的第 k k k 位取反	n xor ( 1 << k )
对整数 n n n 在二进制表示下的第 k k k 位赋值为 1 1 1	n | ( 1 << k )
对整数 n n n 在二进制表示下的第 k k k 位赋值为 0 0 0	n & ( ~ (1 << k) )

二分板子

while(l+1<r)
{
    int mid=(l+r+1)>>1;
    if(check(mid)) l=mid;
    else r=mid;
}
if(check(r)) printf("%d\n",r);
else printf("%d\n",l);
           

while(l<=r)
{
    int mid=(l+r)>>1;
    if(check(mid)) l=mid+1;
    else r=mid-1;
}
printf("%d\n",r);
           

while(l<r)
{
    int mid=(l+r)>>1;
    if(check(mid)) r=mid;
    else l=mid+1;
}
printf("%d\n",l);
           

while(l+1<r)
{
    int mid=(l+r)>>1;
    if(check(mid)) r=mid;
    else l=mid;
}
if(check(l)) printf("%d\n",l);
else printf("%d\n",r);
           

while(l<=r)
{
    int mid=(l+r)>>1;
    if(check(mid)) ans=mid,l=mid+1;
    else r=mid-1;
}
printf("%d\n",ans);
           

动态规划

背包

0/1 背包

for(int i=1;i<=N;++i)
{
    for(int c=C;c>=v[i];--c)
    f[c]=max(f[c],f[c-v[i]]+w[i]);
}
for(int c=0;c<=C;++c) ans=max(ans,f[c]);
           

完全背包

for(int i=1;i<=N;++i)
{
    for(int c=v[i];c<=C;++c)
    f[c]=max(f[c],f[c-v[i]]+w[i]);
}
for(int c=0;c<=C;++c) ans=max(ans,f[c]);
           

多重背包

for(int i=1;i<=n;++i)
{
	if(w[i]*a[i]>C)//如果物品够多，问题就是完全背包
	{
		for(int c=0;c<=C;++c)//完全背包
		{
			if(c>=w[i])
            f[c]=max(f[c],f[c-w[i]]+v[i]);
		}
	}
	else
	{
		int k=1,amount=a[i];
		while(k<amount)
		{
			//是否取一个重量为k*w[i]，价值为k*v[i]的物品
			for(int c=C;c>=k*w[i];--c)
			f[c]=max(f[c],f[c-k*w[i]]+k*v[i]);
			//继续分割
			amount-=k;
			k+=k;	
        }
		//把剩下的作为单独一个物品
		for(int c=C;c>=amount*w[i];--c)
        f[c]=max(f[c],f[c-amount*w[i]]+amount*v[i]);
	}
}	
           

分组背包

for(int i=1;i<=N;++i)
{
    for(int c=C;c>=0;--c)
    {
        for(int k=1;k<=num[i];++k)
        if(c>=v[i][k])
        f[c]=max(f[c],f[c-v[i][k]]+w[i][k]);
    }
}
           

区间 DP

for(int len=2;len<=N;++len)
{
    for(int l=1;l<=N-len+1;++l)
    {
        int r=l+len-1;
        for(int k=l;k<r;++k)
        f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
        f[l][r]+=sum[r]-sum[l-1];// sum[i] 表示前缀和，用来累加答案
    }
}
           

状态压缩

// Shortest Hamilton Path
//  O(n^2*2^n)
int Hamilton(int N)
{
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    for(int i=1;i<(1<<N);++i)
    {
        for(int j=0;j<N;++j)
        {
            if(i>>j&1)
            {
                for(int k=0;k<N;++k)
                {
                    if((i^1<<j)>>k&1)
                    f[i][j]=min(f[i][j],f[i^1<<j][k]+weight[k][j]);
                }
            }
        }
    }
    return f[(1<<N)-1][N-1];
}
           

数论

判素数

//  O(sqrt(N))
bool is_prime(int N)
{
    for(int i=2;i<=sqrt(N);++i)
    if(N%i==0) return 0;
    return 1;
}
           

Eratosthenes 筛法

//  O(NloglogN)
void Eratosthenes(int N)
{
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=N;++i)
    {
        if(vis[i]) continue;
        prime[++m]=i;
        for(int j=1;j<=N/i;++j) vis[i*j]=1;
    }
}
           

线性筛素数

//  O(N)
void primes(int N)
{
    memset(v,0,sizeof(v));
    for(int i=2;i<=N;++i)
    {
        if(!v[i]) v[i]=i,prime[++m]=i;
        for(int j=1;j<=m;++j)
        {
            if(prime[j]>v[i]||prime[j]>N/i) break;
            v[i*prime[j]]=prime[j];
        }
    }
}
           

分解质因数

//  O(sqrt(N))
void divide(int N)
{
    for(int i=2;i<=sqrt(N);++i)
    {
        if(N%i==0)
        {
            prime[++m]=i,c[m]=0;
            while(N%i==0) N/=i,++c[m];
        }
    }
    if(N>1) c[++m]=1,prime[m]=N;
    for(int i=1;i<=m;++i)
    cout<<prime[i]<<'^'<<c[i]<<endl;
}
           

约数集合

//  O(sqrt(N))
void Factor(int N)
{
    for(int i=1;i<=sqrt(N);++i)
    {
        if(N%i==0)
        {
            factor[++m]=i;
            if(i*i!=N) factor[++m]=N/i;
        }
    }
}
           

最大公因数

//  O(log(a+b))
int gcd(int a,int b) { return b?gcd(b,a%b):a; }
           

线性筛欧拉函数

//  O(N)
void Euler(int N)
{
    memset(v,0,sizeof(v));
    for(int i=2;i<=N;++i)
    {
        if(!v[i])
        {
            v[i]=i,prime[++m]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=m;++j)
        {
            if(prime[j]>v[i]||prime[j]>N/i) break;
            v[i*prime[j]]=prime[j];
            phi[i*prime[j]]=phi[i]*(i%prime[j] ? prime[j]-1 :prime[j]);
        }
    }
}
           

扩展欧几里得

int Ex_gcd(int a,int b,int &x,int &y)
{
    if(!b) { x=1,y=0; return a; }
    int d=Ex_gcd(b,a%b,x,y);
    int z=x; x=y; y=z-a/b*y;
    return d;
}
           

图论

两点之间最短路

Floyd

//  O(N^3)
void Floyd()
{
    for(int k=1;k<=N;++k)
    {
        for(int i=1;i<=N;++i)
        {
            for(int j=1;j<=N;++j)
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
        }
    }
}
           

单源最短路

Dijkstra

//  O(MlogN)
void Dijkstra(int st)
{
    priority_queue< pair<int,int> > q;
    memset(dist,0x3f,sizeof(dist));
    memset(vis,0,sizeof(vis));
    dist[st]=0; q.push(make_pair(0,st));
    while(!q.empty())
    {
        int x=q.top().second; q.pop();
        if(vis[x]) continue; vis[x]=1;
        for(int i=head[x];i;i=e[i].Next)
        {
            int y=e[i].y,val=e[i].val;
            if(dist[x]+val<dist[y])
            {
                dist[y]=dist[x]+val;
                q.push(make_pair(-dist[y],y));
            }
        }
    }
}
           

SPFA

//  O(kM) ~ O(NM)  k是一个很小的常数
void SPFA(int st)
{
    queue<int> q;
    for(int i=1;i<=N;++i) vis[i]=0,dist[i]=(i==st)?0:(1<<30);
    vis[st]=1; q.push(st);
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=e[i].Next)
        {
            int y=e[i].y,val=e[i].val;
            if(dist[x]+val<dist[y])
            {
                dist[y]=dist[x]+val;
                if(!vis[y])
                {
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
           

最小生成树

Kruskal

struct rec { int x,y,z; } edge[maxn];
bool operator <(rec a,rec b) { return a.z<b.z; }
int get(int x) { return (fa[x]==x)?x:fa[x]=get(fa[x]); }
void Kruskal()
{
    sort(edge+1,edge+M+1);
    for(int i=1;i<=N;++i) fa[i]=i;
    for(int i=1;i<=M;++i)
    {
        int x=get(edge[i].x);
        int y=get(edge[i].y);
        if(x==y) continue;
        fa[x]=y;
        ans+=edge[i].z;
    }
    cout<<ans<<endl;
}
           

Prim

void Prim()
{
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    d[1]=0;
    for(int i=1;i<N;++i)
    {
        int x=0;
        for(int j=1;j<=N;++j)
        if(!v[j]&&(!x||d[j]<d[x])) x=j;
        v[x]=1;
        for(int y=1;y<=N;++y)
        if(!v[y]) d[y]=min(d[y],a[x][y]);
    }
    for(int i=2;i<=N;++i) ans+=d[i];
    cout<<ans<<endl;
}