数据结构与算法 3. 列表 2021-07-05 浏览量 1308 暂无评论 ## 3.1 接口与实现 向量与列表都属于线性序列。 ### 3.1.1 从静态到动态 从静态(向量)到动态(列表) 静态的数据结构在进行一些动态操作,比如插入、删除时,过程较为繁琐。 ### 3.1.2 从向量到列表 列表采用动态储存策略,其中的元素称为节点,各节点通过指针或引用彼此连接,在逻辑上构成一个线性序列。相邻节点:前驱后继。 ### 3.1.3 从秩到位置 向量支持循秩访问,可在O(1)时间内直接确定其物理位置。 那列表能否沿用这一特性? **循位置访问:** ### 3.1.4 实现 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210702104025941.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210702104100493.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 定义ADT接口 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210702104114999.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 3.2 无序列表 ### 3.2.1 循秩访问 重载[]运算符。 ```cpp template T List::operator[](Rank r) const { Posi(T) p = first(); while (0 < r--) p = p->succ; return p->data; } ``` ### 3.2.2 查找 在节点p的n个前驱中, 找到等于e的最后者。 ```cpp Posi(T) List::find(T const &e, int n, Posi(T) p) const { while (0 < n--) if (e == (p = p->pred)->data) return p; return NULL; } ``` 如果将n与p交换,则表示在p的n个后继中找到等于e的最后者。 ### 3.2.3 插入和复制 ```cpp Posi(T) List::insertBefore(Posi(T) p, T const& e) { _size++; return p->insertAsPred(e); } Posi(T) ListNode::insertAsPred(T const& e) { Posi(T) x = new ListNode(e, pred, this); pred->succ = x; pred = x; return x; } void List::copyNodes(Posi(T) p, int n) { init(); while (n--) { insertAsLast(p->data); p = p->succ; } } void List::insertAsLast(T const& e) { insertBefore(trailer); } ``` ### 3.2.4 删除与析构 ```cpp T LIst::remove(Posi(T) p) { T e = p->data; p->pred->succ = p->succ; p->succ->pred = p->pred; delete p; _size--; return e; } List::~List() { clear(); delete header; delete trailer; } int List::clear() { int oldSize = _size; while (0 < _size) remove(header->succ); return oldSize; } ``` ### 3.2.5 唯一化 ```cpp template int List::deduplicate() { if (_size < 2) return 0; int oldSize = _size; Posi(T) p = first(); Rank r = 1; while ( trailer != (p = p->succ) ) { Posi(T) q = find(p->data, r, p); q ? remove(q) : r++; } return oldSize - _size; } ``` ## 3.3 有序列表 ### 3.3.1 唯一化 ```cpp int List::uniquify() { if (_size < 2) return 0; int oldSize = _size; ListNodePosi(T) p = first(); ListNodePosi(T) q; while (trailer != (q = p->succ)) if (p->data != q->data) p = q; else remove(q); return oldSize - _size; } ``` ### 3.3.2 查找 与无序列表相比并没有什么不同,根本原因在于列表的循位置访问,只能一个接一个,而不能像向量一般循秩访问,可以跳着访问。 ```cpp Posi(T) List::search(T const & e, int n, Posi(T) p) const { while ( 0 <= n--) if (((p = p->data) <= e)) break; return p; } ``` ## 3.4 选择排序 每次选个最大的,很像冒泡啊。 但是冒泡排序的效率很低,有改进的地方。 > 两两交换,小步慢跑 可以直接把最大的移到最后,而不是一步一步地交换。 列表可以这么操作,因为列表的插入不影响别的元素。如果是向量的话,冒泡排序和以下思路的选择排序就没有多大区别了。 ```cpp void List::selectionSort(Posi(T) p, int n) { Posi(T) head = p->pred; Posi tail = p; for (int i = 0; i < n; i++) tail = tail->succ; while (1 < n) { insertBefore(tail, remove(selectMax(head->succ, n))); tail = tail->pred; n--; } } ``` 反思: > insertBefore和remove都需要用到动态内存管理,new, delete,它们的操作时间约为普通操作时间的100倍,可以直接交换数据域。 `selectMax` ```cpp Posi(T) List::selectMax(Posi(T) p, int n) { Posi(T) max = p; for (Posi(T) cur = p; 1 < n; n--) if (!lt((cur = cur->succ)->data, max->data)) // painter覆盖,保证算法的稳定性 max = cur; return max; } ``` 性能: 总体复杂度仍然为$O(n^2)$,但元素移动操作和**比较(暂时还没)**操作比冒泡更少。 ## 3.5 插入排序 打牌理牌。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210705094651132.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ```cpp void List::insertionSort(Posi(T) p, int n) { for (int i = 0; r < n; r++) { insertAfter(search(p->data, r, p), p->data); p = p->succ; remove(p->pred); } } ``` **性能分析** 最好情况$O(n)$,最坏情况$O(n^2)$ ## 3.6 逆序对 将逆序对的个数计算后逆序对的后一个元素上,那么每次插入需要比较的次数就是该元素上逆序对的个数。 假设列表中逆序对的个数为$I$,则插入排序的复杂度为$O(I+n)$,**输入敏感**。 可以把逆序对数量作为无序程度的衡量。 - 阅读全文 -
数据结构与算法 2. 向量 2021-07-04 浏览量 1296 暂无评论 [TOC] # 2.1 接口与实现 向量与列表都属于线性序列。 1. 这种数据结构怎么实现:接口 2. 这种数据结构对应的有效的算法实现,比如 查找、排序 ## 2.1.1 抽象数据类型(ADT)和数据结构 数据结构是基于某种特定的语言,实现ADT的一整套算法。 ## 2.1.2 从数组到向量 内存中连续,数组中的A[i]的物理地址=A + i * s(s为单个元素占用的空间量),故亦称线性数组。 向量是数组的抽象与泛化,由一组元素按线性次序封装而成。 1. 各元素与[0, n)内的秩一一对应 2. **元素类型不限于基本类型** 接口: ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210421185621188.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 2.1.3 Vector模板类 ```cpp typedef int Rank; #define DEFAULT_CAPACITY 3 template class Vector { private: Rank _size; int _capacity; T* _elem; protected: /* ... 内部函数 */ public: /* ... 构造函数 */ /* ... 析构函数 */ /* ... 只读接口 */ /* ... 可写接口 */ /* ... 遍历接口 */ }; ``` **构造与析构** ```cpp Vector(int c = DEFAULT_CAPACITY) { _elem = new T[_capacity = c]; _size = 0; } // 默认 Vector(T const * A, Rank lo, Rank hi) { copyFrom(A, lo, hi); } Vector(Vector const& V, Rank lo, Rank hi) { copyFrom(V._elem, lo, hi); } Vector(Vector const& V) { copyFrom(V._elem, 0, V._size); } ~Vector() { delete [] _elem; } ``` **copyFrom** ```cpp template // T为基本类型,或已重载赋值操作符'=' void Vector::copyFrom(T* const A, Rank lo, Rank hi) { _elem = new T[_capacity = 2*(hi - lo)]; _size = 0; while (lo < hi) _elem[_size++] = A[lo++]; } ``` # 2.2 可扩充向量 使用静态空间管理,容量固定,可能发生上溢或下溢 能否根据实际需要动态调整容量呢? **在即将发生上溢时,适当扩大内部数组的容量** ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210424203647629.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ```cpp template void Vector::expand() { if (_size < _capacity) return; _capacity = max(_capacity, DEFAULT_CAPACITY); T* oldElem = _elem; _elem = new T[_capacity <<= 1]; for (int i = 0; i < size; i++) _elem[i] = oldElem[i]; delete [] oldElem; ``` **容量递增的策略:** 为什么每次要翻倍呢?如果扩充固定大小的容量会怎样呢? 考虑在初始容量为0的空向量中,连续插入m = m*I >> 2 即便不计算申请空间操作,总体复制原向量的耗时(算术级数)为: $I*(m-1)*m/2=O(n^2)$,每次扩容的分摊成本为$O(n)$ 而容量加倍策略的总耗时(几何级数)为$O(n)$ **分摊复杂度:** 对数据结构连续地实施足够多次操作,所需总体成本分摊至单次。 # 2.3 无序向量 ## 2.3.1 循秩访问 使用V.get()和V.put(r, e)接口不便捷,没有下标访问好 **重载下标操作符“[ ]”**,因为返回引用,所以既可以作为右值,又可以作为左值 ```cpp template T & Vector::operator[](Rank r) const { return _elem[r]; } ``` ## 2.3.2 插入 ```cpp template Rank Vector::insert(Rank r, T const & e) { expand(); for (int i = _size; i > r; i--) // 自后向前 _elem[i] = _elem[i-1]; _elem[r] = e; _size++; return r; } ``` ## 2.3.3 区间删除 ```cpp template int Vector::remove(Rank lo, Rank hi) { if (lo == hi) return 0; while (hi < _size) _elem[lo++] = _elem[hi++]; // 从后往前,不能反 _size = lo; shrink(); // 这里为什么_size = lo?,因为这时候lo已经变成_size-hi+lo return hi - lo; ``` ## 2.3.4 查找 对于无序向量,T为可判等的基本类型,或已重载操作符“==”或“!=”; 对于有序向量,T为可比较的基本类型,或已重载操作符“<”或“>” **输入敏感:** ```cpp template Rank Vector::find(T const & e, Rank lo, Rank hi) const { while ((lo < hi--) && (e != _elem[hi])); // hi == lo怎么办呢 return hi; } ``` 注: ```cpp int main(int argc, char** argv) { int a[] = { 0, 1, 2, 3, 4 }; int hi = 4; while ((0 < hi--) && (a[hi] != -1)) printf("%d\n", hi); printf("End: %d\n", hi); } 3 2 1 0 End: -1 ``` ## 2.3.5 单元素删除 [r] = [r, r+1) ```cpp // O(n-r) template int Vector::remove(Rank lo, Rank hi) { T e = _elem[r]; remove(r, r + 1); return e; ``` 为什么不反过来利用单元素删除实现区间删除呢?效率问题,每个单元素删除都要将后继元素前移。 ## 2.3.6 唯一化 剔除重复元素。 ```cpp // 效率太低 template int Vector::deduplicate() { int oldSize = _size; Rank i = 1; while (i < _size) (find(_elem[i], 0, i) < 0) ? i++ : remove(i); return oldSize - _size; } ``` **正确性证明:** 不变性+单调性 不变性:在当前元素V[i]的前缀V[0, i)中,各元素彼此互异 单调性: 前缀长度单调非降,且迟早增至_size 后缀长度单调下降,且迟早降至0 ## 2.3.7 遍历 遍历向量,统一对各元素分别实施visit操作 如何指定visit操作?将其传到向量内部? 1. 利用函数指针机制,只读或局部性修改,为什么?因为函数已经定义了类型 ```cpp template void Vector::traverse(void (*visit)(T&)) { for (int i = 0; i < _size; i++) visit(_elem[i]); } ``` 2. 利用函数对象(重载()操作符)机制,可全局性修改,通用性更强 ```cpp template template void Vector::traverse(VST& visit) { for (int i = 0; i < _size; i++) visit(_elem[i]); } ``` # 2.4 有序向量 无序:能进行比对操作 有序:能进行比较操作 ## 2.4.1 有序性及其甄别 无序向量经预处理转换为有序向量后,相关算法多可优化 ```cpp template int Vector::disordered() const { int n = 0; for (int i = 1; i < size; i++) n += (_elem[i-1] > _elem[i]); return n; } ``` ## 2.4.2 唯一化 观察:在有序向量中,重复的元素必然相互紧邻构成一个区间 ### 低效版 ```cpp template int Vector::uniquify() { int oldSize = _size; int i = 0; while (i < _size - 1) (_elem[i] == _elem[i + 1]) ? remove(i + 1) : i++; return oldSize - _size; ``` 复杂度分析: 最坏情况$O(n-1)+O(n-2)+...+O(1)=O(n^2)$ ### 高效版 将每个重复区间作为一个整体,成批删除,不显示删除,直接把唯一的元素放在前面,去掉后面的区间。 ```cpp template int Vector::uniquify() { Rank i = 0, j = 0; while (++j < _size) if (_elem[i] != _elem[j]) _elem[++i] = _elem[j]; _size = ++i; return j - i; ``` 复杂度:$O(n)$ ## 2.5 有序向量二分查找 版本A [lo, hi) ```cpp template static Rank binSearch(T* A, T const& e, Rank lo, Rank hi) { while (lo < hi) { Rank mi = (lo + hi) >> 1; if (e < A[mi]) hi = mi; else if (A[mi] < e) lo = mi + 1; else return mi; } return -1; } ``` ## 2.7 查找长度 考察关键码的比较次数 有序向量二分查找约1.50logn ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608220129366.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) # 3.1 fib查找构思 二分查找可改进的地方: - 转向左右分支前的关键码比较次数不等,而递归深度却相同 改进思路: 通过递归深度的不均衡,对转向成本的不均衡进行补偿。即向左转向时,分配的长度更长,这样左转向需要的递归深度就变深,右转向的深度变浅 实现: 可以用fib数列进行分配。若设$n=fib(k)-1$,则可取$mi=fib(k-1)-1$,于是,前、后子向量的长度分别为$fib(k-1)-1$和$fib(k-2)-1$ # 3.2 fib查找实例 查找长度 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210630152239793.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 3.3 fib查找实现 ```cpp template static Rank fibSearch(T* A, T const & e, Rank lo, Rank hi) { Fib fib(hi - lo); while (lo < hi) { while (hi - lo < fib.get()) fib.prev()); // 至多迭代几次? Rank mi = lo + fib.get() - 1; if (e < A[mi]) hi = mi; else if (A[mi] < e) lo = mi + 1; else return mi; } return -1; } ``` # 3.4 fib查找最优性 通用策略:对于任何的A[0, n),总是选取$A[\lambda n]作为轴点$, 比如,二分:$\lambda = 0.5$,Fib:$\lambda = 0.618$ ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210630160948316.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) # 4.1 二分查找改进构思 - 二分查找左右转向代价不平衡,那直接让它平衡,减少比较次数 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210630162312523.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 实现 ```cpp template static Rank binSearch(T* A, T const & e, Rank lo, Rank hi) { while (1 < hi - lo) { Rank mi = (lo + hi) >> 1; (e < A[mi]) ? hi = mi : lo = mi; } return (e == A[lo]) ? lo : -1; } ``` ### 缺陷 无论如何,都要查到1 >= hi - lo,即没有单独考虑直接命中mi的情况,最好的情况更坏,最坏的情况更好,性能稳定。 # 4.2 二分改语义 上述查找算法均未严格地兑现search()接口的语义约定:返回不大于e的最后一个元素。 ```cpp template static Ranik binSearch(T* A, T const & e, Rank lo, Rank hi) { while (lo < hi) { Rank mi = (lo + hi ) << 1; (e < A[mi]) ? hi = mi : lo = mi + 1; return --lo; } ``` # 5.1 冒泡排序构思 **原始版本:** 其实已经使用sorted标志进行改进了,如果上一趟没有交换任何两个元素,那么就说明已经有序,程序结束。 ```cpp void bubblesort(int A[], int n) { for (bool sorted=false; sorted = !sorted; n--) for (int i=1; i < n; i++) if (A[i-1] > A[i]) { swap(A[i-1], A[i]); sorted = false; } } template void Vector::bubbleSort(Rank lo, Rank hi) { while (!bubble(lo, hi--)); } template bool Vector::bubble(Rank lo, Rank hi) { bool sorted = true; while (++lo < hi) if (_elem[lo - 1] > _elem[lo]) { sorted = false; swap(_elem[lo - 1], _elem[lo]); } return sorted; } ``` **改进版:** 原始版本中,如果前一部分无序,后一部分有序,扫描交换的趟数不会超过无序前缀的长度,但后部分的有序性并没有利用上。 改进思路:记录最右侧逆序对的位置,作为下一趟冒泡的末尾,这样就能利用有序的后缀,减少趟数,比如无序前缀为326,有序后缀为4589,第一趟后,有序后缀变为45689,最右侧逆序对的位置为4,下一趟只需要对2345排序,而不是234568,这样就有效地利用了后缀的有序性。 ```cpp template Rank Vector::bubble(Rank lo, Rank hi) { Rank last = lo; while (++lo < hi) if (_elem[lo - 1] > _elem[lo]) { last = lo; swap(_elem[lo - 1], _elem[lo]); } return last; } ``` **评价:** 输入含重复元素时,算法的稳定性是更为细致的要求,即保持重复元素的前后位置不变。 上述算法满足稳定性,因为只有在逆序时(>)才交换,等于时不变。 # 6.1 归并排序 分治--合并 主算法 ```cpp template void Vector::mergeSort(Rank lo, Rank hi) { if (hi - lo < 2) return; int mi = (lo + hi) >> 1; mergeSort(lo, mi); mergeSort(mi, hi); merge(lo, mi, hi); } ``` 二路归并 ```cpp template void Vector::merge(Rank lo, Rank mi, Rank hi) { T* A = _elem + lo; // 复制前子向量 int lb = mi - lo; T* B = new T[lb]; for (Rank i = 0; i < lb; B[i] = A[i++]); // 截取后子向量 int lc = hi - mi; T* C = _elem + mi; // 合并 for (Rank i = 0, j = 0, k = 0; (j < lb) || (k < lc); ) { if ( (j < lb) && ( (lc <= k) || (B[j] <= C[k]) ) ) A[i++] = B[j++]; if ( (k < lc) && ( (lb <= j) || (C[k] < B[j]) ) ) A[i++] = C[k++]; } delete [] B; } ``` 二路归并改进 ```cpp template void Vector::merge(Rank lo, Rank mi, Rank hi) { T* A = _elem + lo; int lb = mi - lo; T* B = new T[lb + 1]; for (Rank i = 0; i < lb; B[i] = A[i++]); B[lb] = inf; int lc = hi - mi; T* C = new T[lc + 1]; for (Rank i = 0, j = mi; i < lc; C[i] = A[j++]); C[lc] = inf; Rank j = 0, k = 0; for (Rank i = 0; i < hi - lo; i++) { if (B[j] <= C[k]) A[i] = B[j++]; else A[i] = C[k++]; } delete [] B; } ``` - 阅读全文 -
数据结构与算法 1. 概论 2021-07-03 浏览量 1382 暂无评论 记:清华大学邓俊辉老师[数据结构与算法](https://www.bilibili.com/video/BV1jt4y117KR?from=search&seid=9699712924056767689)视频学习笔记。 [TOCM] # 1. 概论 ## 1.0 知识点 **5个问题:** 1. 什么是计算--课程的目标 2. 什么是好的计算--评判DSA优劣的参照 3. 度量DSA性能的尺度--渐进复杂度,不需要太精细 4. 怎么度量--DSA性能度量的方法 5. DSA的设计及其优化 **2个拓展:** 1. 理论模型与实际性能的差异 2. DSA优化的极限(下界) ## 1.1 计算 对象:规律、技巧 目标:高效、低耗 ### 1.1.1 例子 绳索计算机:垂线 尺规计算机:三等分,包含重复使用的子程序(做平行线) ### 1.1.2 算法 输入:问题 输出:答案 正确性 确定性:由基本操作组成的序列 可行性:可实现,可在常数时间内完成 有穷性:对任何输入,经过有穷次基本操作,都可以得到输出 ### 1.1.3 有穷性 序列Hailstone ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210416225210172.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 不能证明它是有穷的,也没有反例证明它是无穷的 写程序时经常写出死循环,栈溢出。 ### 1.1.4 好算法 **正确:** 符合语法,能够编译、链接,能够处理简单的、大规模的、一般性的、退化的、任意合法的输入 健壮:能辨别不合法的输入并做适当处理,而不致非正常退出 **可读:** 结构化 + 准确命名 + 注释 **效率:** 速度尽可能快,存储空间尽可能少 >Algorithms + Data Structures = Programs >(Algorithms + Data Structures) x Efficiency = Computation ## 1.2 计算模型 正确性:不好数学证明 **成本:** 运行时间 + 所需存储空间 **特定算法 + 不同实例** 如果用$$T_A(P)$$表示算法A求解问题实例P的计算成本,意义不大,因为可能出现的问题实例太多; 如果用$$T_A(n)$$表示算法A求解某一问题规模为n的实例所需的计算成本,仍然存在同一问题等规模的不同实例的计算成本不同(最好情况,最坏情况),应该首先考虑最坏情况; **特定问题 + 不同算法** 如果仅用实验统计,表面上很直接,但不足以准确反映算法的真正效率,因为算法的效率与输入规模、类型,使用的语言、编译器、体系结构、操作系统的状态有关; 所以需要抽象出一个理想的平台或模型:图灵机(Turing Machine)、Random Access Machine(RAM),一般计算工具的简化与抽象,独立于具体的平台,**将算法的运行时间转换为算法需要执行的基本操作次数。** ## 1.3 大O **渐进分析:大O记号** >$$T(n)=O(f(n)), iff \exists c > 0$$ ,当$$n >> 2$$时,有$$T(n) < cf(n)$$. $$\sqrt{5n[3n(n+2)+4]+6} < \sqrt{5n[6n^2+4]+6}< \sqrt{35n^3+6} < 6n^{1.5} = O(n^{1.5})$$. 与$$T_A(n)$$相比,$$f(n)$$更简洁,$$f(n)$$的常系数可忽略,低次项可忽略。 **渐进分析:其他记号** 最好情况(下界):$$T(n)=\Omega(f(n))$$. 中间情况:$$T(n)=\Theta(f(n))$$. **刻度:** 1.$$O(1)$$:2 = 2013 = 2013 x 2013 = O(1). 2.$$logn$$:常底数、常次幂、对数多项式都可以通过数学变换忽略掉 3.$$O(n^c)$$:多项式复杂度,只看最高次 4.$$O(n)$$:线性复杂度 5.$$O(2^n)$$:指数,通常认为不可忍受 ![复杂度](https://img-blog.csdnimg.cn/20210417215204191.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) **一个指数复杂度的例子:** S包含n个正整数,$$\sum{S}=2m$$,S是否有子集T,满足$$\sum{T}=m$$? NP-complete问题 ## 1.4 算法分析 **去粗存精地估算** 两个主要任务 = 正确性(不变性 x 单调性)+ 复杂度 在计算复杂度的时候,真的需要将算法描述为RAM的基本指令,再统计累计的执行次数吗? 不必哦!只要渐进,在渐进的意义下,C++等高级语言的基本指令等效于常数条RAM的基本指令。 **主要方法:** 1. 迭代:级数求和 2. 递归:递归跟踪 + 递推方程 3. 猜测 + 验证 ### 1.4.1 级数 1. 算术级数:与末项平方同阶 ```math \displaystyle T(n)=1+2+3+...+n=n(n+1)/2=O(n^2) ``` 2. 幂方级数:比幂次高出一阶(**咋求的呀**) ```math \displaystyle T_2(n)=1^2+2^2+3^2+...+n^2=n(n+1)(2n+1)/6=O(n^3) ``` ```math \displaystyle \sum{_{k=0}^n} \approx \int{_0^nx^{d+1}dx}= \frac{1}{d+1}x^{d+1}|_0^n=O(n^{d+1}) ``` 3. 几何级数:与末项同阶 ```math \displaystyle T_a(n)=a^0+a^1+a^2+...+a^n=(a^{n+1}-1)/(a-1)=O(a^n) ``` 4. 收敛级数 O(1) 5. **调和级数** ```math \displaystyle h(n)=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\Theta(logn) ``` 6. **对数级数** ```math \displaystyle log1+log2+log3+...+logn=log(n!)=\Theta(nlogn) ``` ### 1.4.2 循环 vs. 级数 可以用画图的方法帮助计算 - 算术级数 ```math \displaystyle \sum{_{i=0}^{n-1}}n = n+n+n+...+n=O(n^2) ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210418210037255.png) ```cpp for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) O1Operation(i, j); ``` - 算术级数 ```math \displaystyle \sum{_{i=0}^{n-1}}i = 0+1+2+...+(n-1)=\frac{n(n-1)}{2}=O(n^2) ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210418210120406.png) ```cpp for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) O1Operation(i, j); ``` - 几何级数 ```math \displaystyle 1+2+4+...+2^{log_2(n-1)}=O(n) ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210418210207859.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ```cpp for (int i = 0; i < n; i <<= 1) for (int j = 0; j < i; j++) O1Operation(i, j); ``` - 几何级数 ```math \displaystyle 0+0+1+2*2+3*4+4*8+...=\sum{_{k=0...logn}(k*2^{k-1})}=O(logn*2^{logn})=nlogn ``` ```math \displaystyle \sum{_{k=0}^n}\lceil log_2k \rceil=O(nlogn) ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210418212709925.png) ```cpp for (int i = 0; i < n; i++) for (int j = 0; j < i; j += j) O1Operation(i, j); ``` ### 1.4.3 取非极端元素 给定整数子集S,|S| >= 3,找出其中既不是最大值,又不是最小值的元素。 常数时间复杂度 ### 1.4.4 冒泡排序 初始版本 ```cpp // 外循环的终止条件是啥?没错,就是sotred,赋值的同时也充当判断条件 void bubblesort(int A[], int n) { for (bool sorted = false; sorted = !sorted; n--) for (int i = 1; i < n; i++) if (A[n-1] > A[i]) { swap(A[i-1], A[i]); sorted = false; } } ``` **分析:** 不变性:经k轮扫描交换后,最大的k个元素必然就位 单调性:经k轮扫描交换后,问题规模缩减至n-k 正确性:经至多n趟扫描惠普,算法必然终止,且能给出正确解答 ## 1.4.5 封底估算(Back-of-the-Envelope) ![在这里插入图片描述](https://img-blog.csdnimg.cn/2021041822493534.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 1.5 迭代与递归 > `迭代乃人工,递归方神通` 但是递归的效率通常不是最佳的,迭代体现出更强的优势 ### 1.5.1 数组求和:迭代 ```cpp int sumI(int A[], int n) { int sum = 0; // O(1) for (int i = 0; i < n; i++) // O(n) sum += A[i]; // O(1) return sum; // O(1) } ``` 分析: > 时间复杂度:O(n),空间复杂度(除输入本身):O(2) > 每循环一次,规模缩小1 > 引出`减而治之` ### 1.5.2 数组求和:线性递归(减而治之) ```cpp sum(int A[], int n) { return (n < 1) ? 0 : sum(A, n-1) + A[n-1]; // 缩减问题 + 平凡问题:可直接求解 } ``` 递归跟踪分析: > ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210419193519188.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) > 时间复杂度:O(n),所有递归实例时间的总和,缩减问题的时间并入子问题 递推方程分析: > T(n) = T(n-1) + O(1) > T(0) = O(1) > 求解: > T(n) - n = T(n-1) - (n-1) = ... = T(2) - T(1) = T(1) - 1 = T(0) ### 1.5.3 数组倒置(减而治之) ```cpp // 递归版 void reverse(int* A, int low, int high) { // 问题规模的奇偶性不变,因为每次变化2,那最后的情况有两种: // 剩最小的奇数1,最小的偶数0,需要两个递归基,low==high,不用变,low > high,不用变 if (low < high) { swap(A[low], A[high]); // 平凡问题 reverse(A, low+1, high-1); // 缩减问题 } } // 迭代原始版 next: if (low < high) { swap(A[low], A[high]); low++; high--; goto next; } // 迭代精简版 while (low < high) swap(A[low++], A[high--]); ``` ### 1.5.4 分而治之 将大规模问题划分为若干个子问题(通常两个),规模**大体相当**,合并子问题的解。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210419200731410.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 数组求和:二分递归 ```cpp sum (int A[], int lo, int hi) { if (lo == hi) return A[lo]; // 递归基 int mi = (lo + hi) >> 2; return sum(A, lo, mi) + sum(A, mi + 1, hi); } ``` 递归跟踪分析: > ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210419202123110.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) > 所有递归实例时间总和(去掉递归调用本身的时间去掉) > $T(n)=O(1) * (2^0, 2^1, 2^2, + ... + 2^{logn})=O(1) * (2^{logn+1}-1)=O(n)$ > 几何级数的总和与末项同阶 递推方程分析: > 递推基:sum(A, lo, lo) > $T(0)=2*T(n/2)+O(1)$,O(1)为归并时间 > $T(1)=1$,为什么这里不是T(0)?因为递推基的规模为1呀 > $$ > T(n) = 2*T(n/2) + c_1 \\ > T(n) + c_1 = 2(T(n/2)+c_1)=2^2*(T(n/4)+c_1) > =... > =2^{logn}(T(1)+c_1) > =2nc_1\\ > =>T(n)=O(n) > $$ ### 1.5.5 Max2 找出数组中最大的两个元素,比较次数尽可能少 迭代1,比较2n-3次 ```cpp void max2(int A[], int lo, int hi, int & x1, int & x2) { for (x1 = lo, int i = lo + 1; i < hi; i++) // 扫描A[lo, hi) if A[x1] < A[i] x1 = i; for (x2 = lo, int i = lo + 1; i < x1; i++) // 扫描A[lo, x1) if A[x2] < A[i] x2 = i; for (int i = x1 + 1; i < hi; i++) // 扫描A(x1, hi) if A[x2] < A[i] x2 = i; } ``` 迭代2,双指针,妙啊,比较次数:最好n-1,最坏2n-3 ```cpp void max(int A[], int lo, int hi, int & x1, int & x2) { if (A[x1 = lo] < A[x2 = lo + 1]) swap(x1, x2); for (int i = lo + 2; i < hi; i++) if (A[x2] < A[i]) if (A[x1] < A[x2 = i]) swap(x1, x2); } ``` 递归 + 分治 ```cpp void max2(int A[], int lo, int hi, int & x1, int & x2) { if (lo + 2 == hi) x1 = (A[lo] > A[lo + 1]) ? A[lo] : A[lo + 1]; if (lo + 3 == hi) { if (A[lo] > A[lo + 1]) { if (A[lo + 1] > A[lo + 2]) { x1 = A[lo]; x1 = A[lo + 1]; } else { if (A[lo] > A[lo + 2]) { x1 = A[lo]; x2 = A[lo + 2]; } else {x1 = A[lo + 2]; x2 = A[lo];} } else { if (A[lo] > A[lo + 2]) { x1 = A[lo + 1]; x2 = A[lo]; } else { if (A[lo + 1] > A[lo + 2]) { x1 = A[lo + 1]; x2 = A[lo + 2]; } else {x1 = A[lo + 2]; x2 = A[lo + 1];} } } } } int mi = (lo + hi) / 2; int x1L, x2L; max2(A, lo, mi, x1L, x2L); int x2R, x2Rl max2(A, mi, hi, x1R, x2R); if (A[x1L] > A[x1R]) { x1 = x1L; x2 = (A[x2L] > A[x1R]) ? x2L : x1R; } else { x1 = x1R; x2 = (A[x1L] > A[x2R]) ? x1L : x2R; } } ``` 分析: > 递推基:问题规模的奇偶性不变,两个递推基: > 1. 大于等于2的最小偶数,2,(为什么要大于2呢?因为要求解两个数呀) > 2. 大于等于2的最小奇数,3 > > 最差情况剩两组大小为3的数组: > $T(n) + 2 = 2(T(n/2)+2)<=2^{log(n/3)}(T(3)+2)=5n/3=>T(n)=5n/3-2$ ## 1.6 动态规划 通过递归找出算法的本质,给出初步解,再将其转化为等效的迭代形式。 ### 1.6.1 FIB **fib():递归** $fib(n)=fib(n-1)+fib(n-2):{0, 1, 1, 2, 3, 5, 8, ...}$ ```cpp int fib(n) { return (n < 2) ? n : fib(n-1) + fib(n-2); } ``` 当n稍微大点(如64)时,运行速度很慢,为什么呢? 直觉上看,它是将一个规模大的问题分解成两个规模小的子问题,这两个子问题有交集,其中一个子问题是另一个问题的子问题。 **递推方程分析:** > 递推基:$T(0) = T(1) = 1;$ > 方程:$T(n) = T(n-1) + T(n-2) + 1$ > 求解:令$S(n)=[T(n)+1]/2$,则$S(0)=1=fib(1),S(1)=1=fib(2)$ > 故$S(n)=S(n-1)+S(n-2)=fib(n+1)$, > $T(n)=2*S(n)-1=2*fib(n+1)-1=O(fib(n+1))=O(\Phi^n)=O(2^n)$ **封底估算:** >$\Phi^{36}=2^{25}, \Phi^{43}=2^{30}={10^3}^3=10^9flo=1sec$ >$\Phi^{5}=10,\Phi^{67}=10^{14}flo=10^5sec=1day$ **递归跟踪:** >![在这里插入图片描述](https://img-blog.csdnimg.cn/20210420192030818.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) >有大量重复的递归实例,能不能每个实例只计算一次? >类比:爬楼梯,每次只能爬1、2阶,到第6阶有几种走法? **fib()回归迭代** 1. 记忆法:将已计算过的实例的结果制表备查 2. 动态规划 颠倒计算方向,由自顶向下递归变为自底向上迭代 两个变量记录当前相邻的两个数,滚动向前 ```cpp f = 0; g = 1; while (0 < n--) { g = g + f; f = g - f; } return g; ``` ### 1.6.2 最长公共子序列LCS **LCS:递归** A[0, n]; B[0, m] 递归基:n = -1 or m = -1, LCS is "" ```cpp if (A[n] == A[m] == 'X') LCS(A[0, n], B[0, m]) = LCS(A[0, n), B[0, m)) + 'X'; // 减而治之 else LCS = max(LCS(A[0, n), B[0, m]), LCS(A[0, n], B[0, m)) // 分而治之 ``` **分析:** >同一个递归实例会被多次唤醒,但实例个数共n+m,其实只需要计算n+m次 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210630154346234.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) **改进:** 颠倒计算方向,从LCS(A[0], B[0])出发依次计算出所有项 ```cpp vertor vecA, vecB; int length[n+1][m+1] = {0}; for (int i = 0; i < n; i++) vecA.push_bask(A[i]); for (int i = 0; i < m; i++) vecA.push_bask(B[i]); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (vecA.at(i) == vecB.at(j)) length[i+1][j+1] = length[i][j] + 1; else length[i+1][j+1] = max(length[i][j+1], length[i+1][j]); } ``` - 阅读全文 -
计算机网络 5. 网络层-控制平面 2021-06-22 浏览量 676 暂无评论 [TOC] ## 5.1 导论 ## 5.2 路由选择算法 如何在网状线路中寻找较好路径,以子网为单位 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210622221108831.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210622221445803.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 找到汇集树,而不是图,因为图可能有环。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210622221655328.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) - 全局路由选择算法(上帝视角)- Link State 在数据结构里叫Dijkstra(迪杰斯特拉)算法。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210622222603788.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210622223149653.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 将自己的链路状态分组泛洪,传遍全网,开启上帝视角。 - 分布式路由选择算法 - Distance Vector - 阅读全文 -
计算机网络 4. 网络层-数据平面 2021-06-21 浏览量 818 暂无评论 [TOC] ## 课程主要内容 - 数据平面、控制平面 - 路由器组成 - IP:格式、分片、IPv4地址、NAT(网络地址转换)、IPv6 - 通用转发和SDN ### 4.1 导论 **网络层服务:** - 在发送主机和接收主机对之间传送**段(segment)** 或UDP数据报 - 在发送端将段封装到数据报中 - 在接收端,将段上交给传输层实体 - 网络层协议存在于每一个主机和路由器 - 路由器检查每一个经过它的IP数据报的头部 **网络层功能:** - 转发:路由器局部,从路由器的哪个端口接收,再从哪个端口发送,依赖于路由表;数据平面 - 传统:目标地址 + 转发表,数据平面与控制平面紧耦合 - SDN:多个字段 + 流表 匹配,转发、block、泛洪或修改字段 - 路由:全局,规划从源主机到目标主机的路径,计算路由表;控制平面 - 传统: - SDN(software-defined network):南桥接口提供流表,控制平面集中 **连接建立:** TCP/IP不需要,ATM需要 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210615223748991.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 4.2 路由器组成 路由:运行路由选择算法/协议,生成路由表 转发:从输入到输出链路交换数据报,根据路由表进行分组的转发 输入输出端口整合在一起。 输入端口缓存: 存在原因:当交换机构的速率小于输入端口的汇聚速度时,在输入端口可能要排队 交换机构: 将分组从输入缓冲区传输到合适的输出端口。 交换速率:理想情况下,交换机构的交换速度是输入线路速度的N倍 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210617162002106.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210617162041966.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210617162320508.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210617162503456.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 4.3 网络层:数据平面 #### IP数据报格式 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210617205433464.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) #### 分片 ![在这里插入图片描述](https://img-blog.csdnimg.cn/2021061721144291.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210617211512305.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) #### IP编址 ##### 子网 ###### IP地址组成 - 子网部分 - 主机部分 ###### 子网概念 - 一个子网内的节点,它们的IP地址高位部分相同; - 无需路由器介入,子网内各主机可以在物理上相互直接到达 互联网的路由以网络(子网)为单位,不然主机到主机路由的话根本不现实。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210617214744340.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ###### Classless InterDomain Routing 子网掩码:11111111 11111111 11111110 0000000 网络号用1表示,主机位用0表示。 示例: 200.23.16.0/23,23表示前23位是网络号。 IP地址以子网为单位进行聚集。 ###### 如何获得IP地址 1. 系统管理员将地址配置在一个文件中 - Wintel:控制面板--网络配置 - UNIX:/etc/rc.config 2. Dynamic Host Configuration Protocol (DHCP) 允许主机从服务器那里动态地获得IP地址(plug-and-play)。 优点: - 无需手动配置 - 节省IP地址 ###### NAT:Network Address Translation 为什么需要: - 本地网络只有一个有效IP地址 意义: - 不需要从ISP分配一块地址,可以用一个IP地址用于所有的局域网设备 - 局域网改动与ISP改动分离 - 局域网内部的设备对外不可见 作用: - 内网地址转换为外网地址 - 外网地址通过端口转换为内网地址 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210620160056807.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 问题: 外网没法主动与内网IP建立连接,NAT穿透问题。 解决方法: - 固定NAT表项; - Universal Plug and Play (UPnP) Internet Gateway Device (IGD)协议,获得NATted主机可以: - 获知网络的公共IP地址 - 列举存在的端口映射 - 增/删端口映射 - 中继服务器 ##### IPV6 IP地址足够多 源主机将分组变小,减轻路由器的负担(通过ICMPv6 [Internet Control Message Protocol]返回“Packet Too Big”) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210620162804859.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210620162814773.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ##### IPV4与IPV6通信 IPV6看作IPV4中的孤岛,各协议内部采用各自的协议通信,IPV6孤岛间通过“隧道”通信,即通过双栈协议建立通信,将V6分组封装到V4中,到另一个岛边缘再解封装。 ### 4.4 通用转发和SDN ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210620165649641.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210620165714883.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210620165731119.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 南向接口向分组交换机下发流表。 - 阅读全文 -