文章目录

c++算法(写于20年2月)

由 笔尖 发布

选择排序:

依次选择最小值放在数组前面,时间复杂度为o(n^2)。

插入排序:

依次将数组中第i个元素向前比较,插入到合适的位置,时间复杂度为o(n^2),且可以提前终止循环,因此在大致有序的前提下,其时间效率甚至超过o(nlogn)。选择排序原来的方式是在第二层循环中不断向前交换元素swap,这种操作较为耗时,因此一个优化方案是,将交换元素改为向后移动元素,最终找到插入的位置。

选择排序由于O(n^2)的系数较小,且可以提前终止,因此常作为高阶排序算法的子过程。

归并排序:

通过递归,将两半有序的数组进行合并,合并成一个新的数组,由于每次二分使得大体循环logn次,在每次循环中,由于合并操作是一个n的复杂度,因此总体为O(nlogn)。

优化方案:

1、如果前半最后的元素<=后半第一个元素,则不进行融合操作,本身就是有序的。

2、当待排序数组大小小于一定阈值时,使用插入排序反而回比归并排序更快,因为n2常数比nlogn小。

还有一种自底向上的归并排序算法,不使用递归,而是二重循环。统计性能上自顶向下更优。

快速排序:

通过递归,每次选择该数组第一个元素进行位置安插,使得其左边元素小于它,右边元素大于它。每次选择安插使得总体循环复杂度为logn,而选择安插的位置这一步操作是n复杂度,因此总的为O(nlogn)。

优化方案:

1、同样的,在数组大小小于某一阈值时,使用更加简单的插入排序,取值100较为优化。

2、如果针对近乎有序的数组进行排序,则会退化为n^2级别算法,因此,不应暴力的直接选取第一个元素进行安插,而是随机选取一个元素,这样复杂度期望为O(nlogn)

3、如果数组size大,而范围小,则会有大量的重复元素,针对这种数组,应当将=的元素分摊到左右两边,否则退化为n^2级别算法。

4、三路快速排序,将数组分为<、=、>三部分后,在对左右两部分进行三路快速排序,这样对于含有大量重复元素的数组比3快。

使用快速排序求解数组第k大的元素,时间复杂度为O(n).\
堆排序:

堆排序是一种动态排序算法,可以在每次增加或者取出元素时动态维护堆的性质。

优化方案:

1、由于添加元素和取出元素都是logn,所以总体是2nlogn复杂度。而通过heapify进行数组建堆,可以少计算一半的元素shiftdown操作,另外建堆操作时间复杂度为O(n)。

2、相比于其他排序算法,多使用了n的空间。其实它可以进行原地堆排序,方法是先进行一次数组建堆,然后从最后一个元素依次向前,每次与第一个元素交换(得到最大值),然后进行异步shiftdown操作,直到遍历结束。

索引堆:

image-20200527160547021

对于这种索引堆,数组只存储了原始数据信息,如果数据类型复杂,则shiftdown、shiftup操作复杂;另外,无法根据索引直修改数据。

image-20200527160559498

为此,多维护一个index数组,每次交换的不是原始数据,而是代表数据的索引。但此时,修改一个元素的时间复杂度还是O(n)。

image-20200527160606325

为此,再多维护一个rev数组,即代表了x号元素在index的第y个。这样,修改元素就变成O(1)的复杂度了,不过紧接的两个shiftup和shiftdown操作仍是O(logn)级别的。

图论:

图的表示有:邻接矩阵(适合稠密图),邻接表(适合稀疏图)

在c++中,数组可以通过[]创建,更高级的做法是是使用向量容器vector,可以动态的扩容、收缩数组大小,并提供对外的高层访问接口。

最小生成树:

有权图,联通整棵树,且分量之和最小。

Lazy Prim算法:当链接上新的点后,立即将该点扩展出去的点(除了已经mark的点)存入最小堆中,循环V-1次,依次从堆中取出最小元素,扩展该点。

Prim算法:更改为最小索引堆,即只存放与点个数相同的元素,扩展点时,除了mark的不选外,还要判断最小索引堆是否包含新的点,如果没有,直接存放堆中,否则比较大小,如果小于之前的大小,则替换掉索引堆对应的元素。

Kruskal算法:将所有边存入最小堆中,依次取出最小边,判断此边对应的点,如果没有相连,则添加此边,否则跳过。

最短路径:

有权图,从一点出发计算到其他点的最短路径。

Dijkstra算法:单源最短路径,无负权边,从源点出发,依次计算到达其他点的路径(排除已经mark的点),如果distto[]中没有到达该点的边,则加入最小索引堆中,如果有且比之前的距离更短,则更新最小索引堆,从堆中取出最短距离的点,重复上述操作。O(V*logV)

Bellman Ford算法:单源最短路径,可以包含负权边,重复V-1次,每次进行distto[]的比较,如果比之前的距离短,则更新distto[],循环结束后,再进行一次上述操作,如果有的距离缩小,则存在负权环,此时,任意一点的距离都是无意义的。O(V*E)

Floyd算法:O(n^3)算法


暂无评论

发表评论