算法性能好坏分析： 时间复杂度 渐近 复杂度分析：时间复杂度 空间复杂度 忽略低阶、常量、系数 代码循环次数最多原则、加法原则、乘法原则 可数的：o(1) 线性的：o(n) 对数：o(logn) o(nlogn)
最好/最坏/平均时间复杂度
空间复杂度 渐近 o(1) o(n) o(n2)
递归算法思想： 概念 条件 问题 递归和循环 常见应用 概念：编程技巧 递回 recursion 递+归 去+回 递推公式 条件：规律（递归表达式）；出口（终止条件） 问题：堆栈溢出（递归深度大，临时变量进入栈，内存不够），不要让递归次数过多； 重复计算（斐波那契数列 1 1 2 3 5 8 13） 递归和循环：静中有动，有去有回；动静如一，有去无回 循环都可写成递归，递归未必能写成循环 耗时较多，重复计算 递归的应用：阶乘问题 BigInteger== big int 数组存大数 一种思路 递归算法应用 目录拷贝
排序 ： o(n) o(n2) 标准：时间复杂度：把低阶、系数、常数也考虑； 空间复杂度：in-place原地排序，out-place占用额外内存； 稳定性：相同元素原有的先后顺序不变 有：冒泡 插入 选择 o(n2)； 归并 快速 o(nlogn)； 桶 计数 基数 o(n)属于线性排序 冒泡bubbleSort：两个位置交换，每次冒泡，有1个到最终位置 时间复杂度 最好o(n) 最坏o(n2)； 空间： o(1)原地； 稳定 插入insertion sort：每个依次插入到排好序的里面； 已排序：首元素 未排序区间 时间复杂度：最好o(n) 最坏o(n2)； 空间：o(1)原地； 稳定 选择selection sort：所有里选最值放最前面 以此类推； 已排序区间：初始为空 未排序区间 时间复杂度：最好o(n2) 最坏o(n2)； 空间：o(1)原地； 不稳定？？ 归并merge sort排序：分治思想 用递归思想来实现。分解+合并 时间复杂度：o(n*logn) 空间：o(n) out-place非原地； 稳定 快速排序quick sort：归并思想 分区点（随机选）pivot 一分为3 分治+递归 时间复杂度：好：o(n)； 坏：o(n2) 空间：o(1) 原地； 不稳定 桶排序bucket sort： 桶-容器 元素值域的划分；待排序元素映射到对应桶上 bucketSize 几种，重复不管（如100个3）；找出元素中最大值和最小值 时间复杂度o(n) 极端情况是o(nlogn)； 空间复杂度：o(N+M) M代表桶个数 空间换时间；是否稳定：取决于桶内元素排序算法 计数排序countingSort：桶排序的延伸，开辟数组，下标的元素个数（统计结果）。输出
二分查找：原理和思想 时间复杂度 实现方法 使用条件及场景 Binary search折半查找例子：猜数字 有序数据 检索区间一半 时间复杂度：o(logn) <常量级复杂度为o(1) 实现：有序数列中不存在重复元素 数组下标 low：指针 序列第一个位置； high：指针 序列最后一个位置； mid：(low+high)/2 while循环 还可以递归实现 实现：有序数列中存在重复元素 重复中的第一个： 重复中的最后一个： 第一个大于等于给定值的元素： 最后一个小于等于给定值的元素： 条件和场景：序列必须是有序的；存储必须是数组；数据量太大或太小不适合用二分查找（太小时循环遍历，数据基于数组，连续内存）
