常用算法

解决任何一个实际问题，都不可避免地涉及到算法的问题。对于一个问题，需要通过一定的算法，得到一个最优（或较优）的方案

常用算法思想

递推算法、枚举/穷举算法、递归算法、分治算法、贪婪算法、 试探算法、模拟算法、动态规划、回溯、双指针

常用排序算法

冒泡、快排、堆、直接选择、直接插入、希尔、归并

常用查找算法

• 有序：二分查找、插值、斐波那契、hash

  要求有序，且物理连续能够随机访问

• 无序：顺序查找、树形、分块（索引）、

评价

• 评价：正确性、高效性、空间性、可读性。
• 效率
  时间复杂度：通过统计算法中基本操作重复执行的次数就可近似地得到算法的执行效率，用O(n)表示
  空间复杂度：

效率

• 时间复杂度： 一个算法执行所耗费的时间。
• 空间复杂度：对一个算法在运行过程中临时占用存储空间大小的量度。

• 常见复杂度由小到大：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

  • 在各种不同算法中，若算法中语句执行次数(占用空间)为一个常数，则复杂度为O(1)；当一个算法的复杂度与以2为底的n的对数成正比时，可表示为O(log n)；当一个算法的复杂度与n成线性比例关系时，可表示为O (n)，依次类推。

  • 时间复杂度记忆

    • 冒泡、选择、插入排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)（一遍找元素O(n)，一遍找位置O(n)）

    • 快速、归并、堆基于分治思想，log以2为底，平均时间复杂度往往和O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）相关

    • 而希尔排序依赖于所取增量序列的性质，但是到目前为止还没有一个最好的增量序列 。例如希尔增量序列时间复杂度为O(n²)，而Hibbard增量序列的希尔排序的时间复杂度为 ， 有人在大量的实验后得出结论;当n在某个特定的范围后希尔排序的最小时间复杂度大约为n^1.3。