数据结构和算法-时间空间复杂度(一)

一、学习背景：
数据结构就是数据+结构，这是大学老师说过的一句话，当时觉得很普通的一句话，随着毕业以后编程工作的时间已经达到2年多，确实感受到数据结构和算法在平时工作中的重要性，这一篇博文主要是记录一下学习过程中一个重要的概念——复杂度分析；
二、概念：
程序的运行其实就是读数据，运算数据和写数据，数据结构和算法解决的是“快和“省”的问题，如何让代码运行的更快，如何让代码更加节省存储空间，那如何来衡量你编写的代码或者算法的代码执行效率呢？我们会想到运行一次不就知道代码的运行速度了，但是由于操作系统的不同，环境的差异，其实同一段代码可能运行的时间是有差异的，我们有没有有一个理论值，下免就带来一个粗略地估算算法执行效率的方法--------大O复杂度表示法。
三、大O复杂度。

1、int cal(int n){
 2、  int sum=0;
 3、 int i=1;
 4、for(;i<=n;i++){
 5、    sum=sum+i;
 6、  }
 7、   return sum
 8、}

上述一个例子来理解一下大O表示法
假如每一段代码执行的时候为t，那么执行cal方法时候，2，3行代码其实就是一个赋值操作，所以都需要一个t，4，5行是一个for循环，执行了n次，所以为nt，所以我们进行一个简单的计算这个方法总共需要多长时间。total=2t+2nt=(2n+2)t,这里我们就可以得出一个结论，所有代码执行的时间T(n)与每行代码的执行次数成正比。
虽然我们不知道t的具体时间，但是通过简单的推论，得到一个规律就是**所有代码的执行时间T(n)与每行代码的执行次数n成正比。
所以大O就要登场了。

T(n)=O(f(n))
介绍一个这个公式：
T(n)表示代码执行的时间，n表示数据规模的大小。
f(n) 表示每行代码执行的次数的总和。

注意：既然大O复杂度计算就是一个估计值，所以说这里并不是具体表示代码真正执行的时
间，而是表示代码执行时间随着数据规模增长的变化趋势，所以，我们可以理解为渐进时间复
杂度，时间复杂度其实就是一个简称。

但是我们又经常看见O(n),O( $n^2$ )，明明计算的时候会很准确的啊，刚刚也介绍了大O时间复杂度只是表示了一种变化趋势，所以我们通常会忽略公式中的常量，低阶，系数，只需要记录一个最大阶的量级就可以了。
所以上述的例子，(2n+2)t 去掉常量和系数，就是O(n)了。
四、时间复杂度分析。
通过上面的记录，已经大体了解了大O时间复杂度的基本概念。如何分析一段代码的时间复杂度，记录三种实用的方法。

1、只关注循环执行次数最多的一段代码

因为大O时间复杂度只表示了一种变化的趋势，忽略了常量，系数和低阶，所以我们只需要关
注代码片段中执行次数最多的代码就可以了，比如上面的程序例子，这个核心代码执行n次，
也就是n的量级，其实真正的时间复杂度就是O(n).

2、加法法则：

一段代码中我们可能只需要关注量级最大的那段代码的时间复杂度即可，也就是说量级最大
的时间复杂度就是这段代码的时间复杂度，这里需要注意一点，就算循环1000次，10000次，
甚至更多次，只要是一个具体的数值，都和n量级扯不上关系，照样也算常量级别的执行时间

3、乘法法则：

嵌套的代码的复杂度等于嵌套内外代码复杂度的乘积
int cal(int m,int n){
   int sum_1=0;
   int i=1;
   for(;i<m;i++){
     sum_1=sum_1+i;
   }
   int sum_2=0;
   int j=1;
   for(;j<n;++j){
     sum_2=sum_2+j;
    }
    return sum_1+sum_2
}
从上述代码可以看出，m和n是两个数量级规模，我们无法事先知道m和n的量级谁大谁小，
所以加法法则这里是行不通的，所以时间复杂度其实是两个的和，O(m+n),这样就不符合大O
时间复杂度的问题了，但是乘法法则是有效的T1(m)*T2(n)=O(f(m)+f(n))

四、内容小结
复杂度可以理解为渐进复杂度，包括了时间复杂度和空间复杂度，是用来分析算法的执行效率
与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行的效率越低，常见的时间复杂度其实并不是很多，从低阶到高阶，O(1),O(logn),O(nlogn),O( $n^2$ )

image.png

时间复杂度的分析给我们编写代码的人员提供了一个很好的理论方向，并且这个和任何平台无关，在一定的性能测试之前，先分析一下时间复杂度和空间复杂度，因此不会浪费太多的时间，给给予我们这种复杂的的分析思想。