常见算法的时间复杂度

时间复杂度 算法分析 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 1、时间复杂度 （1）时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪...

设F(x,y）表示为x，y的最大公约数，取k=x/y，b=x%y,那么x=ky+b，如果一个数能够整除x和y,那么一定可以整除y和b，也就是说，能够整除y和b的数，一定能够整除x和y，所以x和y的公约数和y和b的公约数相同，其最大公约数也相同，则有F(x,y)=F(y,x%y)(x>=y>0),这样就把求两个数的最大公约数转化为求两个更小的数的公约数，直到其中一个数为0，那么另一个数就是两者的最大公约数。φ(n)=n−1，因为质数在大于1的自然数中，除了1和它本身以外不会再有其他因数的自然数。

各常用算法时间复杂度汇总

这是我的推广信息，以激励自己更好的分享自己的知识和经验！也希望看到的你能够多多支持，谢谢！ 1. 滴滴云AI大师: 目前滴滴云正在大力推广自己的云计算服务，需要购买的朋友们用我的AI大师码 「2049」在滴滴云上购买 GPU / vGPU / 机器学习产品可额外享受 9 折优惠，点击这里前往滴滴云官网。 原文地址：7 Helpful Time Complexities 原文作者：Ellis Andrews 译文出自：掘金翻译计划 本文永久链接：https://github.com/xitu/gold.

常见的排序算法  名称 复杂度 说明 备注

需要注意的是，时间复杂度只考虑算法执行时间与输入规模的关系，并不考虑具体的执行时间。线性对数时间复杂度（O(NlogN)）：算法的执行时间介于线性时间复杂度和平方时间复杂度之间。平方时间复杂度（O(N^2)）：算法的执行时间随输入规模的增长而呈二次方增长。对数时间复杂度（O(logN)）：算法的执行时间随着输入规模的增长而增加，但是增长速率较慢。常数时间复杂度（O(1)）：算法的执行时间不随输入规模的增长而变化。指数时间复杂度（O(2^N)）：算法的执行时间随输入规模的增长而呈指数级增长。

插入时间为O(1)，总时间复杂度为O(n)类似先序遍历O(n^2)无向图O(|V|+2|E|)，有向图O(|V|+|E|)O(|V|+|E|)注：普利姆算法不依赖E，适合求解边稠密图的最小生成树；克鲁斯卡尔适合边稀疏而顶点较多的图平均=（ASL成功+ASL不成功）/2。

1、常见的时间复杂度 （1）O(1)：常量阶，运行时间为常量 （2）O(logn)：对数阶，如二分搜索算法 （3）O(n)：线性阶，如n个数内找最大值 （4）O(nlogn)：对数阶，如快速排序算法 （5）O(n^2)：平方阶，如选择排序，冒泡排序 （6）O(n^3)：立方阶，如两个n阶矩阵的乘法运算 （7）O(2^n)：指数阶，如n个元素集合的所有子集的算法 （8）O(n!)：阶乘阶，如n个元素...

一、时间复杂度 常见的时间复杂度量级有： 常数阶O(1) 对数阶O(logN) 线性阶O(n) 线性对数阶O(nlogN) 平方阶O(n²) 立方阶O(n³) K次方阶O(n^k) 指数阶(2^n) 上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。 下面选取一些较为常用的来讲解一下（没有严格按照顺序）： 常数阶O(1) 无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如： int i = 1; int j = 2; ++i; j++;

度量一个程序(算法)执行时间的两种方法 1)事后统计的方法这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。 2)事前估算的方法通过分析某个算法的时间复杂度来判断哪个算法更优. 时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记.

哈希表的插入时间复杂度平均O(1),最好O(1),最差O(n)。 排序链表的插入时间复杂度平均O(n),最好O(1),最差O(n)。 数组的查询时间复杂度平均O(n),最好O(1),最差O(n)。 二叉树的查询时间复杂度平均O(logn),最好O(logn),最差O(n)。 二叉查找树的时间复杂度平均O(logn),最好O(logn),最差O(logn)。 二叉平衡树的时间复杂度平均O(logn),最好O(logn),最差O(logn)。 红黑树的时间复杂度平均O(logn),最好O(logn),最差O(l

本文为转载自CSDN博主「刘望舒」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/itachi85/article/details/54882603 算法的效率 虽然计算机能快速的完成运算处理，但实际上，它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序，我们就需要考虑到算法的效率。 算法的效率主要由以下两个复杂度来评估： 时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的