1、什么是算法？

算法(Algorithm)：一个计算过程，解决问题的方法
image.png

2、递归复习

2.1、递归两个特点：

  • 调用自身
  • 结束条件

2.2、看下面的几个函数：
image.png
博客地址：https://www.cnblogs.com/zhangqigao/articles/6511431.html

3、时间复杂度

时间复杂度：用来评估算法运行效率的一个东西，如图：
image.png
另外再看：
image.png
小结：

  1. 时间复杂度是用来估计算法运行时间的一个式子(单位)。
  2. 一般来说，时间复杂度高的算法比复杂度低的算法慢。(这个只是相对的，比如就算你的程序烂，但是我的配置好呀，对吧。)
  3. 常见的时间复杂度(按效率排序)：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n²logn)<O(n³)
  4. 不常见的时间复杂度(看看就好，忘记最好)：O(n!) O(2ⁿ)O(nⁿ) …..
  5. 如何一眼判断出时间复杂度？ => 1.循环减半的过程 ->O(logn)。 2.几次循环就是n的几次放的复杂度。

    3、空间复杂度

  • 空间复杂度：用来评估算法内存占用大小的一个式子

  • “空间换时间”

    4、列表查找

    1、列表查找：从列表中查找指定元素

  • 输入：列表、待查找元素

  • 输出：元素下标或者查找到元素

2、顺序查找

  • 从列表第一个元素开始，顺序进行搜索，直到找到为止。

3、二分法查找

  • 从有序列表的候选去 data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。

4、顺序查询和二分查找时间复杂度
image.png