算法刷题介绍

算法刷题介绍

课程大纲

Python 作为实现语言。

• 快速排序算法 0 (nlogn)

  • 实际工作中要根据实际情况选择最优解。 有可能没有完美方案，需要做平衡。

• 数据有啥特征？

  举例：对一组数据进行排序

  • 是否包含大量重复元素（三路快排）
  • 是否近乎有序的数据（插入排序）
  • 数据是否有固定的取值范围（计数有序）
    • 是否需要稳定排序？（归并排序更好）

• 数据存储时使用的数据结构

  • 如果是使用链表存储的（归并排序）
  • 数据是否可以全部装入内存（外排）

算法复杂度介绍

• 算法复杂度中大O的含义

  大O复杂度表示法

  复杂度分析是估算算法执行效率的办法，公式O(f(n))表示算法的复杂度，此方法即为 大O复杂度表示法
  O(f(n))中n表示数据规模，f(n)表示运行算法所需要执行的指令数。
  1
  2

  

  数据规模

  通过刚才的例子我们可以得出如下结论，如果想在1s之内解决问题：

  空间复杂度

  • 解决问题时，多创建了一个数组：O(n)
  • 解决问题时，多创建了一个二维数组：O(n^2)
  • 解决问题时，用到了几个临时的变量：O(1)
  

• 简单的复杂度分析

  时间复杂度分析

  

  • 关于O(logn)

    

    简单复杂度分析：

    1：关注循环执行次数最多的那一段代码
    2：总复杂度等于量级最大的那段代码的复杂度
    3：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
    4：当两段代码的数据规模不同时，不能省略复杂度低的部分
    5：复杂度中对数的部分通常忽略底数
    1
    2
    3
    4
    5

• 递归算法的复杂度分析

  

  在递归中只做了一次递归调用

  递归深度为D

  在每个递归函数中，时间复杂度为T

  总体时间复杂度为O(T*D)

  

  递归算法的复杂度分析：

  1：只调用一次递归的，计算递归深度
  2：多次调用递归的，计算调用次数
  1
  2

• 最好/最坏/平均/均摊复杂度分析

  最好、最坏、平均时间复杂度分析

  

  均摊复杂度分析

  

  • 均摊复杂度：就是把过程复杂度操作所耗费时间分担到简单操作上

    对一个数据结构进行一组连续操作，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，适合运用均摊复杂度分析代码

  总结：

  1. 面试时讨论的时间复杂度主要是平均时间复杂度
  2. 均摊复杂度：把过程复杂操作所耗费时间分担到简单操作上

常用排序算法介绍

• 冒泡排序

  冒泡排序（Bubble Sort）是一种很原始的排序方法，就是通过不断地交换“大数”的位置达到排序的目的。
  因为不断出现 “大数” 类似于水泡不断出现，因此被形象地称为 冒泡算法。
  
  冒泡算法的基本原理：比较相邻两个数字的大小。将两数中比较大的那个数交换到靠后的位置。
  不断地交换下去就可以将最大的那个数放到队列的尾部。然后重头再次交换，直到将数列排列成有序数列。
  1
  2
  3
  4
  5

  

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kgwptDVt-1668843863167)(https://s1.vika.cn/space/2022/11/19/5d1251ed4b23442598dbcf73c24b1dbe)]

  冒泡排序原理：

  1. 通过不断地交换 “大数” 的位置达到排序的目的
  2. 冒泡排序的时间复杂度是O(n^2)

• 选择排序

  与冒泡排序相比，选择排序算法（Selection Sort）的原理更加简单粗暴，就是在数列中不断地找最小（大）的那个数。
  
  选择排序算法的基本原理：从数列中选择最大（最小）的那个数，将这个数放到合适的位置，然后再删除这个数的子数列中选择最大（最小）的那个数，将这个数放到合适的位置......直到子数列为空。
  1
  2
  3

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cHpZtr5P-1668843863168)(https://s1.vika.cn/space/2022/11/19/4b6b6785e6914b558069916a222d2fec)]

  

  选择排序原理：

  1. 不断将数列中的最小值交换到数列头部实现排序
  2. 选择排序的时间复杂度是0(n^2)

• 插入排序

  插入排序（Insertion Sort）很容易理解，插入排序方法与打扑克牌的排序很相似。在打扑克时，每抓一张新牌，都会与手上已有的牌进行比较，将新派插入到比自己小的牌后面。在取完所有的牌后，手上已有的牌就是个有序的序列。
   
  插入排序原理：首先将数列分成两部分。 数列的第一个数为left部分，其他的数为right部分。然后将right部分中的数逐一取出，插入left部分中合适的位置。 当right部分为空，left部分就成为了一个有序数列。
  1
  2
  3

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PUit8VVd-1668843863169)(https://s1.vika.cn/space/2022/11/19/8e15a25c720b403a9de669a5d4b26838)]

  

• 归并排序

  归并排序（Merge Sort）是一种典型的递归法排序。它把复杂的排序过程分解成一个简单的合并子序列的过程。
  
  归并排序原理：先将数列分成左右两份（最好是等分），然后将左、右子数列排序完毕后再合并到一起就成了一个有序数列左、右两个子数列变成有序数列的过程是一个递归过程：再把子数列分成左、右两份，把子子数列排序完毕后合并成子数列...
  1
  2
  3

  

  归并排序原理：

  1. 将数列不断分成两组直到不能再分，在合并时排序
  2. 归并排序的时间复杂度是O(nlogn)

• 快速排序

  快速排序（Insertion Sort）也是一种递归排序算法。
  
  快速排序原理：先以列表中的任意一个数为基准（一般选头或尾），将列表分为左、右两个子列表：
  左子列表的数要比基准数小，右子列表的数要比基准数大。 然后继续把左子列表和右子列表按同样的方法继续分解、比较，直到分无可分。最后将左子列表（比基准数小）+基准数+右子列表（比基准数大）连接起来得到一个有序数列。
  1
  2
  3
  4

  

• 计数排序

  计数排序（Counting Sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H.Seward 提出的。
  
  计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。
  然后根据数组C来将A中的元素排到正确的位置。
  1
  2
  3
  4

  

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WF1OuGPN-1668843863170)(https://s1.vika.cn/space/2022/11/19/3cce076246ee44b29f6d0892a9c1b3cf)]

  

  计数排序代码：

  

  计数排序原理：

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为i的元素出现次数，存入数组C的第i项
  3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
  4. 反向填充目标数组：将每个元素ii放在新数组的第C[i]项，每放一个元素就将C[i]减去1
     出待排序的数组中最大和最小的元素
  5. 统计数组中每个值为i的元素出现次数，存入数组C的第i项
  6. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
  7. 反向填充目标数组：将每个元素ii放在新数组的第C[i]项，每放一个元素就将C[i]减去1