一、算法的概念
基本概念
解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
一个问题可以有很多中算法，每种算法都有不同的效率。
一个算法具有五个特征：有穷性、确切性、输入项、输出项、可行性
二、时间复杂度和空间复杂度的概念
算法评定
算法分析的目的在于选择合适算法和改进算法。
一个算法的评价主要从时间复杂度和空间复杂度来考虑。
1.时间复杂度
执行算法所需要的计算工作量。一般来说，计算机算法是问题规模 n 的函数 f(n)，算法的时间复杂度也因此记做 T(n)=O(f(n))
问题的规模n越大，算法执行的时间的增长率与 f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）
（1）时间复杂度计算方式
得出算法的计算次数公式
用常数1来取代所有时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶存在且不是1，则去除与这个项相乘的常数
（2）举例
常见时间复杂度：常数阶 O(1)、线性阶 O(n)、平方阶 O(n^2)、立方阶 O(n^3)、对数阶 O(log2n)、nlog2n阶、指数阶
复杂度大小：O(1) > O(log2n) > O(n) > O(nlog2n) > O(n^2) > O(n^3) > O(2^n) > O(n!) > O(n^n)
（3）时间复杂度其他概念
最坏情况：最坏情况时的运行时间，一种保证，如果没有特别说明，说的时间复杂度即为最坏情况的时间复杂度
平均情况：期望的运行时间
2.空间复杂度
算法需要消耗的内存空间，记住 S(n) = O(f(n))
包括程序代码所占用的空间，输入数据所占用的空间和辅助变量所占用的空间这三个方面
计算和表示方法和时间复杂度类似，一般用复杂度的渐近性来表示
空间复杂度计算方式
有时用空间换取时间
冒泡排序的元素交换，空间复杂度 O(1)
三、常见算法
1.排序算法
冒泡排序、直接插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序
① 冒泡排序
原理：两两相邻的数进行比较，如果反序就交换，否则不交换
时间复杂度：最坏（O(N^2)），平均（O(n^2)）
空间复杂度：O(1)
② 直接插入排序
原理：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序
时间复杂度：最坏（O(n^2)），平均（O(n^2)）
空间复杂度：O(1)
③ 希尔排序
原理：将待排序的数据根据增量分成几个子序列，对子序列进行插入排序，直到增量为1，直接进行插入排序；增量的排序，一般是数组的长度的一半，再变成原来增量的一半，直到增量为1
时间复杂度：最差（O(n^2)），平均（O(n*log2n)）
空间复杂度：O(1)
④ 选择排序
原理：每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
时间复杂度：最坏（O(n^2)），平均（O(n^2)）
空间复杂度：O(1)
⑤ 快速排序
原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归完成
时间复杂度：最差（O(n^2)），平均（O(nlog2n)）
空间复杂度：最差（O(n)），平均（O(log2n)）
⑥ 堆排序
原理：把待排序的元素按照大小在二叉树位置上排序，排序好的元素要满足：父节点的元素要大于等于子节点；这个过程叫做堆化过程，如果根节点存放的是最大的数，则叫做大根堆，如果是最小，就叫小根堆，可以把根节点拿出来，然后再堆化，循环到最后一个节点。
时间复杂度：最差（O(nlog2n)），平均（O(nlog2n)）
空间复杂度：O(1)
⑦ 归并排序
原理：将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列
时间复杂度：最差（O(nlog2n)），平均（O(nlog2n)）
空间复杂度：O(n)
总结：快速排序、归并排序的理想时间复杂度都是O(nlog2n)，但是快速排序的时间复杂度并不稳定，最坏情况下复杂度为O(n^2)，所以最理想的算法还是归并排序
2.查找算法
① 二分查找
原理：从数组的中间元素开始，如果中间元素正好是要查找的元素，搜索结束，如果某一个特定元素大于或者小于中间元素，则在数组大于或者小于中间元素的那一半中查找，而且跟开始一样从中间开始比较，如果某一步骤数组为空，代表找不到。
时间复杂度：最差（O(log2n)），平均（O(log2n)）
空间复杂度：迭代（O(1)）、递归（O(log2n)）
② 顺序查找
原理：按一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止。
时间复杂度：最差（O(n)），平均（O(n)）
空间复杂度：O(1)
总结：二分查找算法的时间复杂度最差是O(log2n)，所以二分查找法更快，但是递归情况下，二分查找要消耗内存，时间复杂度为 O(log2n)
解题方法
此类考点非常重要也较为复杂，需要考生充分理解各种排序算法和查找算法的原理以及实现方式，另外还需要理解时间复杂度和空间复杂度的计算方式和概念，此类靠差点是考察考生的逻辑思维能力，因此需要仔细研究各种算法的实现方式。
备注：需要对其他常见的算法进行练习