环球观点：数据结构刷题2023.02.18小记

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

环球观点：数据结构刷题2023.02.18小记

2023-02-18 10:55:03 来源：博客园

(相关资料图)

连通分量

一个无向图的连通分量是其极大的连通子图无向图中任意两个节点之间有连通，则称为连通图。每一个非连通图可分为几个极大连通部分，每一个极大连通子图称为连通分量；极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边；极小连通子图既要求保持图连通，又要使得边数最少的子图。

顺序循环队列

顺序循环队列 Q 空的条件是： Q.front==Q.rear.

排序算法的存储开销

考察的是不同排序方式的空间复杂度。归并排序存储开销大。快速排序：选一个基准值进行左右分区，比基准小的放到左边，比基准大的放在基准右边。空间复杂度为O(logn )堆排序：利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。空间复杂度为O(1)归并排序：先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表。空间复杂度为O(n)插入排序：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。空间复杂度为O(1)

拓扑排序算法

有向无环图才能进行拓扑排序拓扑排序：由一个集合上的一个偏序来得到集合上的一个全序。所以只能用在有向图中，且如果有向图存在环的话也无法得到图的所有节点，所以拓扑排序只能用在无环有向图中

筛选法建堆

用筛选法建堆，必须从值为n/2的数据开始建初始堆

插入法建堆的时间复杂度

O(nlog(n))

关键词：空间复杂度连通分量时间复杂度