初始数据结构--先导篇

作为一个文科生转行过来的程序媛，数据结构和算法的概念对我来说都是很难。虽然平时工作几乎很少用到算法，但是我总觉得如果不懂数据结构，在工作里面，我几乎不会去考虑业务之外的东西，比如性能，比如操作数组的时候，什么方法是最优的，这些都是隐藏需求。是我需要去突破的地方。

所以我决定硬着头皮啃一下试试。（主要还是跟着老师学，能不能学懂我没有太多信心，但是我希望我可以）
那从今天就进入数据结构和算法的美妙世界吧！

目的

学习数据结构和算法本身需要解决什么问题？
“快” 和“省”! 让代码运行更快，让我的代码更优雅，更节省存储空间。

鸡血😄

我们学习数据结构和算法，并不是为了死记硬背几个知识点。我们的目的是建立时间复杂度、空间复杂度意识，写出高质量的代码，能够设计基础架构，提升编程技能，训练逻辑思维，积攒人生经验，以此获得工作回报，实现你的价值，完善你的人生。
我被开篇的鸡血给打醒了， 哈哈哈哈

第一课，我学到的知识

• 学习复杂度分析的好处

老师讲了很多关于复杂度分析的好处，和事后统计法的区别。但是我个人粗浅的理解是：不用事后统计，在写代码的时候就考虑自己写的代码的时间,空间复杂度，就能有效粗略估计算法的执行效率，事先的预防成本肯定是低于代码写好以后再来优化的成本的。

• 大O 复杂度表示法

从CPU 的角度来看，代码的执行都是重复着：读数据-运算-写数据 的步骤。当我们写出来的每一段代码，如何“肉眼”估算他的计算时间呢？

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

上面这个例子。for 循环之外的代码都是运行一次，for 循环里面的代码运行n 次。所以复杂度就是T(n)

 int cal(int n) {
   int sum = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1;
     for (; j <= n; ++j) {
       sum = sum +  i * j;
     }
   }
 }

这次的代码里面有两个for 循环，还是嵌套的for 循环，那么第一个for 循环的运行次数是n ，第二个是n²

重要点：
所有的代码执行时间T(n） 和每行代码的执行次数n 成正比 总结成公式就是

T(n) = o(f(n))

这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

时间复杂度分析

• 只关注代码里面循环次数最多的一段代码，并且排除掉常量，低阶, 系数。
  这个道理还是很好理解的吧，因为影响代码运行的最长时间，就是最复杂的那个。那些常量不管是多大，他都只会执行一次而已，无法对渐进时间复杂度产生影响，
• 加法法则
• 乘法法则： 嵌套代码的复杂度等于嵌套内外复杂度的成绩
  这个需要说明一下

int cal(int n) {
   int ret = 0; 
   int i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i);
   } 
 } 
 
 int f(int n) {
  int sum = 0;
  int i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
 }

这样的嵌套循环里，整个 cal() 函数的时间复杂度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n2)。

贴一个老师总结的复杂度量级

3723793cc5c810e9d5b06bc95325bf0a.jpg

对于以上的几种复杂度，我来谈一下我自己的理解

• O(1)
  代码只会执行一次，是复杂度最低的，一般来说，只要代码里不存在循环语句，递归语句，正常的代码执行，不管多少行，他的复杂度都是O(1)

• O(logn)、O(nlogn)

一般的循环，都可以归为这种的复杂度里面, 这里再次套用一下老师的一个例子

 i=1;
 while (i <= n)  {
   i = i * 2;
 }

这个例子里面，变量i 从1开始，每循环一次就乘以2，大于n 的时候才结束。
老师说这里是高中数学里面的等比数列。我就恍然大悟，然后再去复习了一下等比数列和对数。
这里代码的复杂度是 x=log2n 实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。

对数之间是可以互相转换的，log3n 就等于 log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

• O(m+n)、O(m*n)
  这个代码的复杂度是由两个数据的规模来决定的。

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 是表示两个数据规模，我们不知道两个谁的量级更大，所以就是 ：T1(m)*T2(n) = O(f(m) * f(n))。
上面的例子是这里其实我没太理解，不过我感觉我应该用不到这么复杂的，就先不追究了

空间复杂度分析

其实空间复杂度分析和时间复杂度分析很类似。看下面的例子

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

在这个例子里面，首先我们申请了一个 i 的空间变量, 他是常量阶的，和数据规模n 没有关系，在for 里面，申请了一个n 长度的数组。所以整个代码的空间复杂度是O（n)
我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。
所以我暂时按照时间复杂度分析 的规律来理解空间复杂度，应该没有什么问题吧。

课后思考

有人说，我们项目之前都会进行性能测试，再做代码的时间复杂度、空间复杂度分析，是不是多此一举呢？而且，每段代码都分析一下时间复杂度、空间复杂度，是不是很浪费时间呢？你怎么看待这个问题呢？

针对这个问题，其实从我个人而言，我粗浅的理解为： 对代码进行分析，就会和host 没有关系，对代码进行性能测试的话，可能受浏览器的内核，版本等等之类的影响。还有一个先后顺序的问题，但是实际上在工作中，普通的项目，做了其一应该就ok 了吧。