思考能力是人最重要的核心竞争力，而算法是为数不多能有效训练大脑思考能力的途径之一

什么叫数据结构，什么叫算法

1. 数据结构：在计算机科学中，数据结构（英语：data structure）是计算机中存储、组织数据的方式。 上面这个是wiki百科中关于数据结构的定义。
2. 算法：
   • 一个有限指令集，
   • 接受一些输入（有时候不需要输入）
   • 产生输出
   • 一定在有限步骤后终止
   • 每一条指令必须明确

一般来说，广义上讲数据结构，就是指一些数据的存储结构。算法就是操作数据的方法。
以图书馆储藏书籍举例，管理员将书籍分门别类进行存储。按照一定的规律编号，就是书籍这个数据的存储结构。
而在查找一本书的时候，可以一本本找，也可以根据书籍类别编号等信息定位同类型位置在依次查找。这些查找的方法就是算法。
而狭义的讲代指某些著名的数据结构和算法，例如队列，栈，堆，二分查找，动态规划等

数据结构和算法的关系

数据结构和算法是相辅相成的，数据结构是为算法服务的，算法腰作用在特定的数据结构之上

算法的优劣

image.png

复杂度分析

• 空间复杂度S(n):根据算法写成的程序在执行时占用存储单元的长度。(S : space ) SN = C * N
• 时间复杂度T(n):根据算法写成的程序在执行时耗费时间的长度。（T: time）
  所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比
  T(n) = O(f(n)) O 表示代码执行时间T(n) 与f(n)表达式成正比。
  这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度

//如下代码，假设每行代码执行时间都一样 为个unit_time
//2、3行代码分别需要1个unit_time 4、5行都执行了n遍 需要2n
//所以此段代码执行时间为（2n + 2）* unit_time
int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) { 
    sum = sum + i;
   } 
   return sum;
 }
/**
*  2、3、4各需要1个unit_time
* 5、6需要2n * unit_time  7、8 执行了n^
* 则总时间为T(n) = (2n^ + 2n + 3) * unit_time
*/
 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;
     }
   }
 }

上述代码，当n趋于无穷大时，公式中低阶、常量、系数三部分对增长趋势的影响无限趋于1，所以可以忽略。T(n) = O(n)； T(n) = O(n^2)

时间复杂度分析

1. 只关注循环执行次数最多的一段代码
   大O这种复杂度表示方法只是表示一种变化趋势，通常可以忽略掉公式中的常量、低阶、系数，只需要记录最大阶的量级就就可以了。在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了

// 此段代码。2、3行都是常量级的执行时间，与n大小无关，所以对于复杂度没有任何影响
//循环影响4、5行代码。所以总的时间复杂度为O(n)
 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度。
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

常见时间复杂度分析

image.png
对于上述复杂度量级，粗略的分为多项式量级、非多项式量级.
把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

1. O(1):常量级时间复杂度的一种表示方法，并不是指只执行一行代码。一般情况下，代码执行时间不随n增大而增大，这样的记为O(1)。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
2. O(logn)/O(nlogn)

//O(log2n)
//2^0  2^1  2^2 .... 2^x = n
//x = log2n
 i=1;
 while (i <= n)  {
   i = i * 2;
 }
//O(log3n)
 i=1;
 while (i <= n)  {
   i = i * 3;
 }

对数之间是可以互相转换的，log3n 就等于 log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。同理，根据乘法法则，如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

3. m+n / m*n

//从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 
//和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用
//加法法则，省略掉其中一个。所以，代码的时间复杂度就是 O(m+n)。
//针对这种情况，原来的加法法则就不正确了，需要将加法规则
//改为：T1(m) + T2(n) = O(f(m) + g(n))。
//但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(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;
}

空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。