算法复杂度分析

算法复杂度分析

执行代码，通过统计，监控等工具，计算算法的执行时间，占用的内存大小等。这种方法叫做事后统计法。      缺点：a 测试结果非常依赖测试环境      b 测试结果受数据规模的影响很大     时间复杂度分析方法      1.只关注循环次数最多的一段代码      2.加法法则：总复杂度等于量级最大的那段代码的复杂度      3.乘法法则：嵌套代码的复杂度：等于嵌套内外代码复杂度的乘积   几种常见时间复杂度：      1.O(1)     只要复杂度不随着n的增长而增长，都视为O(1)           一般情况下，只要不存在循环语句，递归语句，即使有成千上万行代码也是O(1)        2.O(logn)  O(nlogn)            Log2n * log32 = log3n                Log2n = x ——> 2的x次方 = n           O(nlogn)复杂度：将一段时间复杂度为O(logn)执行n次     常见算法：归并排序，快速排序        3.O(m+n)  O(m*n)   常见空间复杂度：     O(1)  O(n)   O(n*n)  不会出现指数形式的空间复杂度，主要看申请的空间数量 复杂度大小排序： O(1)  <  O(logn)  <  O(n)  <  O(nlogn)  <  O(n*n)   最好，最坏情况时间复杂度 分别指的是最理想的情况下时间复杂度，以及最糟糕情况下的时间复杂度   平均时间复杂度分析： 多数情况下，我们不考虑最好，最坏时间复杂度，只有当存在一定的量级差异时才去计算   均摊时间复杂度

原文链接:https://www.cnblogs.com/wangzepu/p/11328471.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有