算法学习

2021-03-09 本文已影响0人黑铁选手

1、算法可以让代码可行、高效、低占用资源明白代码底层逻辑，方便使用和阅读
2、算法基本要素/特性：输入、输出、有穷性、确定性、可行性
3、学习方法：多看，多练，多思考

算法刷题.png

时间复杂度.png

二分法查找算法注意事项：
1、先决条件：有序数组（后面大于前面）链表不适合二分法
2、注意数据类型是有范围的才用L+（R-L）/ 2表达式更合适
3、注意 start = mid+1 和end = mid -1防止死循环
4、数据量不可过大
数组：连续存放，便于查找链表：不要求连续，结点后面需要添加下一个结点的首地址，缺点：不便于查找

链表和数组时间复杂度比较.png

数组和链表的选择.png

线性表：里面的数据以线性关系排列，数据一旦存放，其位置就不变
顺序表：连续存放数组（地址连续，类型相同），引用数组，动态数组
数组元素的位置称为索引，利用所以可以计算出元素对应的存储地址，索引从0开始
数组支持直接访问
引用数组：解决了数据类型必须一致的问题
动态数组：list(Python), ArrayList(java)，用空间换取时间，提供更多的存储空间
链表常见面试题：

链表常见面试题.png

1，4，5，8面试常见
栈和队列（保存临时数据）
栈：先进后出LIFO（栈看成一个桶，往桶里面放东西），队列：先进先出FIFO（队列看成一个管，向管里注水）

栈的操作

队列操作

双端队列

双端队列操作

栈和队列常考题

栈常见题型.png
初级排序算法：
选择排序：
不断遍历数组，选择数组中最小值的元素，放在数组前面最小元素后面，如果是第一个元素最小，就不变，后面依次选择最小数排在后面。

特点：运行时间和输入无关，数据移动最少，时间复杂度O(n**2)，空间复杂度O(1)

冒泡排序：
从头开始选择相邻两个元素进行比较，如果前面大于后面，则交换位置，一直到最后一个元素，最后一个元素为最大数。除最后一个元素外，针对其他元素，进行重复操作，直到剩下最后一个数，没有任何数字比较。
特点：运行时间和输入无关，时间复杂度为O(n**2)，空间复杂度为O(1)

插入排序：
从第一个元素开始，该元素视为已经排序，取出下一个元素，与排好序的元素进行比较（从后向前比较），如果新元素小于排好序的元素，则把新元素插入到该元素位置，该元素移动到下一个位置，重复插入操作，如果找到已排序的元素小于等于新元素时，把新元素插入到该位置后，重复步骤，直到排序结束
特点：数组中每个元素距离他最终位置都不远，一个有序的大数组接一个小数组，数组中只有几个元素的位置不正确，很快速

希尔排序：
把待排序的数组分为若干组，让然后每个组内进行插入排序操作，再对已经排好序的组进行插入排序操作。
特点：各个子数组都很短，排序后子数组都是部分有序的，最坏时间复杂度根据步长序列不同而不同，目前已知最好的是O(nlog 2 n)，最优时间复杂度是O(n)
希尔排序采用3H+1方式分组 H 从0开始取值

归并排序算法：主要采用分治法（按照数组下标将数组拆分成左右两个长度相等的小数组），所谓分治法就是把原问题分解成若干个可以解决的简单问题，可以直接求解，原文的解就是若干子问题解的合并。分治三步骤：分解、解决、合并问题。
五大常用算法思想：分治、动态规划、贪心、回溯、分支界定
归并排序时间复杂度为O(nlog n)
归并排序优化：使用插入排序处理规模较小的子数组，提高时间

快速排序：核心思想（分治），按照某一个元素的大小将数组拆分成左右两部分
主要步骤就是选取一个元素作为基准值，将数组中小于基准值的元素排在基准值前面，大于基准值的排在后面（分割操作），递归地把小于基准值的子数列和大于基准值的子数列排序。
注：何为递归：程序调用自身的编程技巧称为递归（ recursion）在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。递归和循环的区别：循环是有去无回，递归式有去有回
举个栗子，你用你手中的钥匙打开一扇门，结果去发现前方还有一扇门，紧接着你又用钥匙打开了这扇门，然后你又看到一扇们..但是当你开到某扇门时，发现前方是一堵墙无路可走了，你选择原路返回——这就是递归
但是如果你打开开一扇门后，同样发现前方也有一扇们，紧接着你又打开下一扇门..直到打开最后一扇门出去，或者一直没有碰到尽头(死循环)——这就是循环。