天天观焦点：数据结构刷题2023.02.20小记

手机

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

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

天天观焦点：数据结构刷题2023.02.20小记

2023-02-20 10:53:22 来源：博客园

(资料图片仅供参考)

排序算法最坏时间复杂度

A：归并排序，是稳定排序，需要一个栈来维护，利用分治法思想每次分成两边分别排序再合并，具有稳定性，无论何时，其时间复杂度均为 O(NlogN).B:快速排序，最坏情况下是 O(N^2),平均和最好是 O(NlogN).C:冒泡排序，无论何时时间复杂度都是 O(N^2).D:插入排序，最坏和平均时间复杂度是O(N^2)，最好是 O(N).

迪杰斯特拉算法

链接：https://www.nowcoder.com/questionTerminal/6db3fe3195524ef69b098df91ffb94f0来源：牛客网

单源是什么意思？从一个顶点出发，Dijkstra算法只能求一个顶点到其他点的最短距离而不能任意两点。算法思想：维护一个集合 S，集合内的点是已经确定最短路径的结点；每次操作找出与集合相邻的点中距离起点最近的结点加入集合中，并确定它的最短路径值为它的前一已确定结点的最短路径值+该边权值，存在dis数组中。算法流程：首先把结点1加入集合（红色结点），蓝色结点为相邻结点， s={1}，dis[]={0,∞,∞,∞,∞,∞,∞,∞}与S相邻的结点为2、3、5，把相邻结点路径最短的加入集合（即结点5） s={1,5}，dis[]={0,1,∞,∞,∞,∞,∞,∞}与S相邻的结点为2、3、6、8，把相邻结点路径最短的加入集合（即结点3） s={1,5,3}，dis[]={0,1,2,∞,∞,∞,∞,∞}与S相邻的结点为2、4、6、8，把相邻结点路径最短的加入集合（即结点2和4） s={1,5,3,2,4}，dis[]={0,1,2,3,3,∞,∞,∞}与S相邻的结点为6、7、8，把相邻结点路径最短的加入集合（即结点8） s={1,5,3,2,4,8}，dis[]={0,1,2,3,3,4,∞,∞}与S相邻的结点为6、7，把相邻结点路径最短的加入集合（即结点6和7） s={1,5,3,2,4,8,6,7}，dis[]={0,1,2,3,3,4,5,5}

用俩个栈模拟实现一个队列，如果栈的容量分别是O和P(O>P)，那么模拟实现的队列最大容量是多少？

关键词：时间复杂度最短路径最大容量