算法与数据结构(一)：时间复杂度与空间复杂度

最近突然萌生了一个想法，好好系统的学习一下算法与数据结构然后产生一系列的文章来回顾与总结学到的东西，这部分我想从最简单的部分一一介绍总结，包括一些很基础的内容

为什么要学习数据结构与算法

以前在学校的时候就知道 程序 = 算法 + 数据结构，程序的作用是用来处理与解决现实问题，而在描述与解决现实问题时不可避免的会涉及到数据，如何将这些数据有效的组织起来并利用一定的方法来运算与处理应该算是程序的核心问题。

当然如果仅仅将编程作为谋生的手段，确实不用太关心这部分，现实中很多语言和库都封装了这些东西，需要的时候直接用即可，不懂算法与数据结构并不会对编程产生什么影响，在实际工作中可能并没有机会自己实现一个链表、队列等等。但是如果真正热爱这一行，希望能更上一层楼的，算法与数据结构必定是绕不开的一环。

学习数据结构并不是为了要在工作中自己实现它，而是:

• 了解使用算法解决问题的一些思想，能够让你知道如何更好地优化自己的代码
• 了解更多的数据结构与算法的知识，能在编程中更加游刃有余，能更好的解决实际问题
• 程序的性能瓶颈往往都跟算法和数据结构有关系， 好的算法能更多的提升程序的性能
• 当我们面对一个完全未知的问题时，了解更多的算法知识能够多出一些尝试
• 为了能够在面试中脱颖而出

当时在学校学习的时候我是被各种系统程序以及各种漂亮的Web程序给吸引了，认为算法这种东西永远都在处理平时根本碰不上的问题，有时间浪费在这些虚无缥缈的东西上还不如学学怎么做一个应用，写一个网站出来。那个时候基本放弃了对这方面的学习。后来在工作中经常出现网上对你所面临的问题没有明确的结局方案，需要在现有的方案上做修改，这个时候就束手无策了。使用了某种算法解决了问题，但是效率不高，遇到大规模访问时容易出错崩溃，这个时候还是没辙。还有就是在网上看别人的开源代码时需要花额外的精力来研究老外的某个写法，其实如果懂点算法的知识，可能并不需要这些额外的时间开销。

由于有了这些精力，我想在新年开始的这段时间里研究一下数据结构与算法的相关内容，提升一下自己的基本功。

时间复杂度

有了前面说的一些经历，下面就进入正题了：算法的时间复杂度与空间复杂度；

时间复杂度与空间复杂度是评价一个算法好话的一个常用标准。时间复杂度是以程序代码中基本语句执行次数作为衡量标准。换句话说时间复杂度是用这个算法需要执行代码量来评价的。

假设一个问题的规模为n，常见的比如说有n个数据需要进行处理，如果算法是类似这样的:

for(int i = 0; i < n; i++)
{
   //do some thing
   setup1();
   for(int j = 0; j < n; j++)
   {
     //do something
     setup2();
   }
}

假设setup1和setup2 函数执行了j、k次运算 那么我们来计算一下这个算法总共执行了多少次：

首先在内层循环中循环了n次，那么setup2函数执行了nci，这个时候有 k * n , 外层循环也是执行了n次，所以这个算法总共执行了 n * (j + n * k) = n^2 + n(k + j) , 这样得到事件复杂度为 T(n) = n^2 + n(k + j) 由于k j都是常数，所以计算这个时间复杂度又可以写作 T(n) = n^2 + nt , 对于这个表达式取自高次幂 得到这个算法的时间复杂度为 T(n) = n^2

从上面的计算来看，计算事件复杂度就是计算它需要执行基本代码执行多少次，然后将得到的表达式取最高次幂并去掉系数。

常见的时间复杂度有O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(n^k)、O(n!)、O(2^n)

从效率上看，它们是依次降低的。一般来说算法最多达到O(n^2), 如果比O(n^2)高，这个时候就需要好好考虑一下优化算法了。

一般常见的算法时间复杂度如下:

• 每层循环，时间复杂度都需要在原来的基础之上乘以n
• 没有循环的时间复杂度一般为常数
• 二分法时间复杂度为logn

空间复杂度

空间复杂度是指算法占用内存空间的值，需要注意的是，这个内存占用主要是在算法内部动态分配了内存，算法函数中的临时变量储存在栈空间，算法执行完成后会回收，一般不考虑局部变量占用的内存。同时静态变量，全局变量都不考虑进来

在算法中值考虑在函数中分配的内存以及递归调用时栈空间的占用内存。

计算算法的空间复杂度并不复杂，因此这里就不给例子了。算法的空间复杂度应该控制在O(1)，也就是尽量不要在算法内部分配内存，少用递归。