算法：解决问题的方法和步骤不同的算法解决相同的问题，算法的成本是不同的，总体上来讲，一个优秀的算法追求两个目标：1、在程序中，占用最少的内存空间去完成需求2、花最少的时间去完成需求结论：算法研究的是如何花最少的时间和占用最少的内存空间去完成相同的需求算法是一种解决问题的方法，我们需要将：时间占用和空间占用量化，有关算法的时间耗费分析，我们称为算法的时间复杂度分析，算法空间的耗费分析，我们称为空间的复杂度分析1、时间维度：是指执行当前算法所消耗的时间，时间越短，算法越好这么认为：代码执行次数越多，耗费时间越长，效率就越差，我们需要多写一些短小精悍的代码来提高代码的执行效率时间复杂度：看作是一个代码执行的时间趋势，执行次数与执行参数息息相关，如果一个问题的规模是n，解决这个问题的某一算法所需要的时间T（n）算法的时间复杂度说的是：一个算法的执行时间根据数据规模增长的一个趋势40亿的数据要求搜索，线性查找法：最坏的情况，40亿条数据，40亿次操作二分查找：最多32次操作就可以完成算法的时间复杂度：即算法的时间度量T（n）= O(f(n)) // 大O表示法O：后面的括号，括号中是一个函数。指明某个算法耗时与数据增长量之间的关系。n：代表的是输入数据的量T：代表的是算法需要执行的总时间大O表示法：表示代码执行时间随是数据规模增长的变化趋势，时间复杂度表示的是变化趋势，并不是真正的执行时间分析算法的时间复杂度时：1、算法完成工作最少需要的基本操作，最优的时间复杂多2、算法完成工作最多需要的基本操作，最坏的时间复杂度3、算法完成工作平均需要的基本操作，平均时间复杂度对于最优的时间复杂度，意义不大，因为他没有提供有用的信息，它反映的是最乐观的以及最理想的情况，没有参考价值最坏的时间复杂度，提供了一种保证，表明算法在这个程序的基本操作中一定能完成需求平均时间复杂度，是对算法的一个比较全面的评价，不是每一个计算都能够在这个基本操作中完成常见的时间复杂度：1、常数阶：O（1），T（n）= O（1），时间复杂度是常数级别的，表示无论n的规模如何增长，它的执行时间基本是不变的，常数阶是最低的时间复杂度。2、线性阶：O（n），T（n）= O（n），代表数据量增大几倍，耗时也增大几倍，常见的算法：遍历3、平方阶：O（n²）,T（n）= O（n²），代表的是数据量增大n倍时，耗时增大n的平方倍，两层循环4、立方阶：O（n³），T（n）= O（n³），代表的是数据量增大n倍时，耗时增大n的立法倍，三层循环5、对数阶：O（log n），T（n）= O（log n），当数据增大n倍时，耗时增大log n倍，二分查找，n以倍数的规模递减6、线性对数阶：O（nlog n），T（n）= O（nlogn），就是n乘于logn，当数据增大n倍，耗时会增大n*logn倍7、指数阶：O（2²）当数据增大n倍时，耗时增大2²倍计算时间复杂度1、基本操作，即只有常数项，认为这个时间复杂度就是O（1）2、顺序结构，时间复杂度按加法3、循环结构：时间复杂度按乘法4、分支结构：时间复杂度取最大值判断一个算法的效率的时候，往往只需要取关键操作数量的最高次项优劣对比：O（1）< O（log n）< O（n） < O（nlog n） < O（n²）< O（n³）< O（2²）越小表示算法的执行时间越短，算法效率越高2、空间维度：是指执行当前算法所消耗的内存空间S（n）= O（f（n））空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，表示的是：算法存储空间于输入值之间的关系通常来讲，只要我们的算法不涉及到动态的空间，递归，栈，空间复杂度通常为常数O（1）算法的空间复杂度，并不是计算实际占用的空间，而是计算整个算法的辅助空间单元（变量）的个数，与问题的规模没有关系，空间复杂度主要是看新开辟的变量个数
若有收获，就点个赞吧
0 人点赞
