数据结构和算法刷题笔记.pdf下载
找工作简历模板集(word格式)下载
Java基础核心知识大总结.pdf下载
C/C++常见面试题（含答案）下载
设计模式学习笔记.pdf下载
Java后端开发学习路线+知识点总结
前端开发学习路线+知识点总结
大数据开发学习路线+知识点总结
C/C++(后台)学习路线+知识点总结
嵌入式开发学习路线+知识点总结
提到数据结构+算法的学习，有两个问题是不可避免的，一个是时间复杂度，可以理解为算法的运行时间，如果算法运行时间太长，那这个算法就没法用；另一个是算法的空间复杂度，可以理解为把算法存储在计算机中需要多大的空间，如果需要空间太大，那这个算法也没法用。因此，需要对一个算法的时间复杂度和空间复杂度进行分析，来确定该算法的可行性。
时间复杂度的分析，一般有两种方法：事后统计法事前分析法
事后统计法是用测试程序和数据来运行已编写好的算法，对其执行时间进行比较。这种方法看似可以精确的计算算法的执行时间，但存在一些不足：一是使用事后统计法的一个前提是，算法已编写好，而编写算法需要大量时间和精力，同时测试程序和数据的准备也是耗时巨大的，这就会出现算法编写好了，测试之后发现用不了的情况，白白浪费大量时间和精力。二是算法的运行依赖计算机硬件和软件因素。同一个算法在不同的计算机上执行时间是不一样的。在不确定这个算法会用在什么样的计算机上时，少量的测试结果不具备可靠性。三是算法的执行时间受数据规模的影响。比如对于几个数字的排序，不论是使用选择排序还是插入排序，亦或是快速排序，其执行耗时的差异基本没有。事前分析法是不依赖具体的测试程序和数据，根据统计方法对算法执行效率进行分析的方法。01时间复杂度大O记法那么，如何在不运行代码的情况下对代码的执行效率进行分析呢？来看一个例子。publicvoidcalculateSum(intn){intsum=0;//执行一次for(inti=0;in;i++){//循环执行n次intbase=i;//循环执行n次for(intj=0;jn;j++){//循环执行n*n次sum+=base+j;//循环执行n*n次}}}
?
假设每个代码语句每执行一次的耗时是一样的，记为unitTime，所有代码的执行时间，记作T(n)。基于此，上述代码的执行总耗时为T(n)=(1+n+n+n*n+n*n)unitTime=(2n2+2n+1)unitTime。根据T(n)=(2n2+2n+1)unitTime，可以得出结论：对于一个算法来说，其所有代码的执行总时间T(n)与其每行代码的执行次数n成正比。对于T(n)=(2n2+2n+1)unitTime来说，由于unitTime表示代码中一条语句执行一次的耗时，在这里要分析的是代码执行总时间T(n)和代码执行次数n之间的关系，因此可以不考虑unitTime。此外，2n2+2n+1表示的代码语句的执行总次数，可以将其抽象为f(n)=2n2+2n+1。也就是说，我们用f(n)来抽象表示一个算法的执行总次数。因此可以推导出所有代码的执行总时间T(n)和每行代码的执行次数n之间的关系是：T(n)=O(f(n))公式中的O表示代码的执行总时间T(n)和其执行总次数f(n)成正比。这种表示法，称之为大O记法。大O记法T(n)=O(f(n))，表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，表示的是算法的渐近时间复杂度，简称时间复杂度。02时间复杂度分析时间复杂度分析有一个基本的法则，就是四则运算法则。一是加法法则，如果算法的代码是平行增加的，那么就需要加上相应的时间复杂度。二是乘法法则，如果算法的代码增加的是循环内的嵌套或者函数的嵌套，那么就需要乘上相应的时间复杂度。
如下代码是我们在推导大O记法时用到的，最后推导出其时间复杂度是T(n)=O(2n2+2n+1)，在推导过程就用到了加法法则和乘法法则。
publicvoidcalculateSum(intn){intsum=0;//执行一次for(inti=0;in;i++){//循环执行n次intbase=i;//循环执行n次for(intj=0;jn;j++){//循环执行n*n次乘法法则sum+=base+j;//循环执行n*n次乘法法则}}}
第二行代码的时间复杂度是T2(n)=1;第三行、第四行代码的时间复杂度分别是T3(n)=O(n)，T4(n)=O(n)；第五行和第六行代码它们本身会执行n次，但由于是在循环内，所以根据乘法法则，其时间复杂度分别是T5(n)=O(n2)，T6(n)=O(n2)。
最后根据加法法则，整段代码的时间复杂度就是:T(n)=T2(n)+T3(n)+T4(n)+T5(n)+T6(n)=O(1)+O(n)+O(n)+O(n2)+O(n2)=O(2n2+2n+1)三是减法法则，如果是去掉算法中平行的代码，就需要减掉相应的时间复杂度。四是除法法则，如果是去掉嵌套内的循环或函数，就需要除去相应的时间复杂度。对于减法法则和除法法则就不做具体示例说明了，接着我们看下时间复杂度分析另外几个常用的结论：加法常数项可以忽略
除去最高阶项，其它次项可以忽略
与最高次项相乘的常数可以忽略
接着依次解释下。加法常数项可以忽略如下图，算法B与算法A相比，在不同的执行次数下，算法B都是劣于算法A的。在将算法B的加法常数项1和算法A的加法常数项3去掉后，得到算法B1和算法A1，但此时，在不同的执行次数下，算法B1还是劣于算法A1。由此可知，加法常数项对算法的复杂度几乎无影响。除去最高阶项，其它次项可以忽略如下图，算法B相比于算法A，少了加法常数项2和次低项2n。但是，随着执行次数n的增大，算法A的执行效率越来越趋近与算法B。因此，在进行算法的时间复杂度分析时，应主要