建筑工程网站大全,杭州网络推广专员,什么犁网站做淘宝门头,网页设计公司建网站网站设计一、衡量算法好坏的指标 时间复杂度衡量算法的运行速度#xff0c;空间复杂度衡量算法所需的额外空间。这些指标#xff0c;是某场景中选择使用哪种数据结构和算法的依据。如今#xff0c;计算机的存储器已经变得容易获得#xff0c;所以不再太关注空间复杂度。
二、渐进表…一、衡量算法好坏的指标 时间复杂度衡量算法的运行速度空间复杂度衡量算法所需的额外空间。这些指标是某场景中选择使用哪种数据结构和算法的依据。如今计算机的存储器已经变得容易获得所以不再太关注空间复杂度。
二、渐进表示 复杂度是一个渐进表示它不代表算法的运行速度或者利用的额外空间的实际值而是代表它们与数据规模 N 输入到算法中的数据量相关的变化趋势。因此复杂度更高的并不代表实际的运行时间更长实际运行时间由数据规模、算法复杂度、计算机的硬件性能共同决定。 不同规模的时间复杂度比较 1 logn n nlogn n^2 n^3 2^n n! n^n
三、最好、平均、最坏复杂度
最好最好情况下的复杂度。最坏最坏情况下的复杂度最常考虑的。只要考虑了最坏情况所有情况都没问题了平均所有情况(发生的概率x执行次数)之和。
四、时间复杂度的计算 关键是计算出算法的基本操作比如算术计算、比较等的执行次数。其次只取最高次项并去掉系数。为什么要去掉系数、非最高项比如一个算法的基础操作执行次数是 N^2 N若 N1,0000结果为 1,0001,0000这时 1,0000 相对于 1,0001,0000 就是一个很小的数目对结果没有多大影响可以忽略。
1、例1 T(n) O(n^2)
2、例2 T(n) O(1)
3、例3 T(n) O(n^2) 直接写3个赋值语句和调用函数在执行效率上有差别但是我们不需要深究。实际上在编译时Swap 函数调用会被直接替换成3个赋值语句因为在 java 中存在 inline 体系编译器会自动识别哪些方法应该进行 inline 操作这样的目的就是提高执行效率。
4、例4 T(n) O(logn)注省略底的log默认底为2。
5、例5 T(n) O(2^n)数据规模稍微大点执行效率将非常慢。
五、空间复杂度 注意空间复杂度是执行算法所需要的额外空间所以进入算法前已经消耗的空间是不算数的。
1、例1 T(n) O(1)
2、例2 T(n) O(n)
3、例3 T(n) O(n)
