1 入门基础与简介

1 课程介绍

• 课程时间为两个半月，共二十几节课，具有连贯性，希望同学们尽量不要缺席。
• 课程内容包括入门基础、基础数据结构与算法、进阶版的高级数据结构、高效查找和搜索引擎技术等专项学习，最后是总结。
• 基础数据结构
  • 数组：一组相同类型的变量的集合，它们在内存中是连续存储的。
  • 链表：一种线性数据结构，其中的每个元素都是一个节点，每个节点包含数据和指向下一个节点的指针。
  • 栈：一种特殊的线性表，其插入和删除操作只能在表的一端进行，这一端被称为栈顶，另一端被称为栈底。
  • 队列：一种特殊的线性表，其插入操作在表的一端进行，而删除操作在表的另一端进行，这两端分别被称为队头和队尾。
• 基础算法
  • 排序算法：将一组数据按照某种顺序排列的算法，如冒泡排序、插入排序、选择排序、快速排序、归并排序等。
  • 查找算法：在一组数据中查找某个特定元素的算法，如顺序查找、二分查找、哈希查找等。
  • 图算法：处理图这种数据结构的算法，如图的遍历、最短路径、最小生成树等。
  • 动态规划：一种解决多阶段决策问题的算法，通过将问题分解为多个子问题，并保存子问题的解，来避免重复计算。
  • 分治算法：将一个大问题分解为多个小问题，然后分别解决这些小问题，最后将小问题的解合并起来得到大问题的解。
  • 贪心算法：在每一步都选择当前最优的决策，而不考虑整体的最优解。
  • 回溯算法：一种通过尝试所有可能的选择来解决问题的算法，当遇到不满足条件的选择时，会回溯到上一步并尝试其他选择。
  • 递归算法：函数直接或间接调用自身的算法。
  • 字符串算法：处理字符串的算法，如字符串匹配、字符串编辑距离等。
  • 数值算法：处理数值计算的算法，如数值积分、数值微分等。

2 数据结构与算法介绍

• 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，包括数组、链表、栈、队列等。
• 算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
• 数据结构与算法的重要性在于它们是计算机科学的基础，是解决实际问题的关键。

3 思考题讲解

判断一个数是否为二的 N 次方？【2、4、8、16是的，6、10不是】

• 普通解法

  • 可以通过将该数不断除以 2，直到商为 1 或余数不为 0。
  • 如果商为 1，则该数为二的 N 次方；否则，该数不是二的 N 次方。
  • 这种方法的时间复杂度为 O(logN)，空间复杂度为 O(1)。

• 位运算讲解

  • 介绍：位运算是指对二进制位进行操作的运算，包括与、或、异或、取反、左移、右移等。位运算可以用于优化算法，提高程序的效率。例如，可以使用位运算来判断一个数是否为奇数或偶数，或者计算一个数的二进制表示中 1 的个数。

  • # 解题思路
    1:01
    2:10  01 & 10 =00
    4:100
    3:011 4&3==0
    8:1000
    7:0111
    16:10000
    15:01111  ===>转化成了 if(n&(n-1) == 0) 那么n就是2的次方 n  > 1
    

4 算法的重要性

1. BAT 一线互联网公司必问技术：数据结构与算法是所有计算机的基础，大企业看重的是潜力，只有技术扎实，才有潜力承担更多的责任。
2. 业务工程师必备技能：如果不想做一辈子的 crud 工程师，想做成架构师，就必须要去学习数据结构与算法，要知道它的底层原理，这样才能走得更深，摆脱 crud 工程师的标签。
3. 架构师必备技能：写出框架级的代码，能提供 api 给别人来操作，需要学习数据结构与算法，才能设计出好的框架。
4. 提升自己的能力，不被行业淘汰：计算机行业发展很快，只有把数据结构这样的课程学好，才能抵御中年危机。

5 学习数据结构与算法的方法

1. 看书：推荐 严蔚敏版《数据结构与算法》和《大话数据结构》。
2. 刷题：力扣:https://leetcode-cn.com/ 和 POJ[北京大学题库：http://poj.org/] or HDU[杭州大学题库：https://acm.hdu.edu.cn/]。

6 算法的特征和设计原则

1. 特征：有穷性、确定性、可行性、有输入有输出。
2. 设计原则：正确性、可读性、健壮性。

7 算法的时间复杂度

算法的时间复杂度是衡量算法效率的重要指标，它表示算法执行的时间与问题规模之间的关系。

O(1)>O(logn)>O(n)>O(nlogn)>O(n^2)>O(nx)

O(1)>O(logn)>O(n)>O(nlogn) 效果都是很好的。几乎优化的空间不是很大。

优化的目标就是要往O（1）的方向接近。

常数时间复杂度 O(1)

• 表示算法的执行时间不受输入数据规模影响，总是固定的。

• 例如，下面的代码的时间复杂度为 O(1)：

• int a = 1;
  

对数时间复杂度 O(logn)

• 算法执行时间随输入数据规模增长而对数增长。

• 例如，二分查找算法。

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

线性时间复杂度 O(n)

• 算法执行时间随输入数据规模线性增长。

• 例如，遍历数组或链表。

• for (int i = 0; i < n; i++) {
      a = a + 1;
  }
  

线性对数时间复杂度 O(nlogn)

• 算法执行时间随输入数据规模增长而线性对数增长。

• 例如，归并排序算法、堆排序。

• for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
          a = a + 1;
      }
  }
  

平方时间复杂度 O(n^2)

• 算法执行时间随输入数据规模增长而平方增长。

• 例如，冒泡排序算法。

• for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
          a = a + 1;
      }
  }
  

N次方时间复杂度 O(n^n)

• 算法执行时间随输入数据规模增长而呈N次方增长。

• 这类算法在实际应用中往往性能较差，因为它们处理大规模数据时非常耗时。

• for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
          for (int k = 0; k < n; k++) {
              a = a + 1;
          }
      }
  }
  

如何确定时间复杂度

确定算法的时间复杂度通常涉及以下步骤：

1. 找到循环
   • 分析算法中的循环结构，特别是嵌套的循环。
   • 计算循环体执行的次数，这通常与输入数据规模有关。
2. 考虑网络请求和远程调用
   • 如果算法涉及网络请求（如RPC、远程调用、分布式系统通信或数据库请求），这些操作通常具有不可预测的执行时间。
   • 在分析时间复杂度时，可能需要将这些操作视为常数时间复杂度（O(1)），因为它们的具体执行时间取决于网络条件和外部系统性能。
3. 忽略低阶项和常数因子
   • 当评估算法的整体时间复杂度时，通常可以忽略低阶项和常数因子，因为它们对算法性能的影响相对较小。
4. 考虑最坏情况
   • 在分析时间复杂度时，通常关注算法在最坏情况下的性能，因为这为我们提供了算法性能的上限。

8 算法的空间复杂度

一、空间复杂度的概念

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为算法本身所使用的指令、常数、变量和输入数据所占用的存储空间，以及算法在运行过程中临时占用的存储空间。

二、空间复杂度的计算
空间复杂度的计算方法与时间复杂度类似，都是通过分析算法的执行过程来确定的。在计算空间复杂度时，需要考虑以下几个方面：

1. 算法本身所使用的存储空间：这包括算法中使用的常量、变量、指针等所占用的存储空间。
2. 输入数据所占用的存储空间：这包括算法输入数据所占用的存储空间，例如数组、链表、树等数据结构所占用的存储空间。
3. 算法在运行过程中临时占用的存储空间：这包括算法在运行过程中为了实现某些功能而临时分配的存储空间，例如递归函数在调用过程中所使用的栈空间、动态规划算法中所使用的数组等。

三、常见的空间复杂度

1. 常数阶：常数阶的空间复杂度为 O(1)，表示算法在运行过程中所占用的存储空间大小为一个常数。例如，下面的代码的空间复杂度为 O(1)：

int a = 1;

1. 线性阶：线性阶的空间复杂度为 O(n)，表示算法在运行过程中所占用的存储空间大小与输入规模成线性关系。例如，下面的代码的空间复杂度为 O(n)：

int[] array = new int[n];
for (int i = 0; i < n; i++) {
    array[i] = i;
}

1. 平方阶：平方阶的空间复杂度为 O(n^2)，表示算法在运行过程中所占用的存储空间大小与输入规模的平方成线性关系。例如，下面的代码的空间复杂度为 O(n^2)：

int[][] matrix = new int[n][n];
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        matrix[i][j] = i * j;
    }
}

四、空间复杂度的优化
空间复杂度的优化是算法设计中的一个重要问题，它可以通过以下几种方式来实现：

1. 数据结构的选择：选择合适的数据结构可以有效地降低空间复杂度。例如，使用数组来存储数据时，空间复杂度为 O(n)，而使用链表来存储数据时，空间复杂度为 O(1)。
2. 算法的优化：通过对算法进行优化，可以减少算法在运行过程中所占用的存储空间。例如，使用动态规划算法来解决问题时，可以通过减少数组的维数来降低空间复杂度。
3. 空间的复用：在算法的执行过程中，可以通过复用已经分配的存储空间来降低空间复杂度。例如，在递归函数中，可以通过使用栈来复用已经分配的存储空间。

总结

1. 算法与数据结构是计算机科学的基础，是解决问题的重要工具。
2. 时间复杂度是衡量算法运行效率的重要指标，它表示运行一个代码所要花费的时间。
3. 空间复杂度是衡量算法占用内存空间的重要指标，它表示算法在运行过程中所占用的内存空间大小。
4. 常见的时间复杂度有常数阶、对数阶、线性阶、线性对数阶、平方阶、N 次方阶等。
5. 常见的排序算法有冒泡排序、快速排序、归并排序、堆排序等，它们的时间复杂度分别为 O(n^2)、O(nlogn)、O(nlogn)、O(nlogn)。