考察的重点

• 算法的时间复杂度和空间复杂度
• 三大算法思维：贪心，二分，动态规划
• 常见数据结构

算法复杂度

什么是复杂度

• 程序执行时需要的计算量和内存空间(和代码是否简洁无关)
• 复杂度是数量级(方便记忆、推广)，不是具体的数字
• 一般针对一个具体的算法，而非一个完整的系统

时间复杂度(程序执行时需要的计算量)

• O(1)一次就够(数量级)
• O(n)和传输的数据量一样(数量级)
• O(n^2)数据量的平方(数量级) 例如：两个for循环
• O(logn)数据量的对数(数量级) 例如：二分法
• O(n*logn)数据量数据量的对数(数量级) 一个for循环，一个二分法

空间复杂度(程序执行时需要的内存空间)

• O(1)有限的、可数的空间(数量级
• o(n)和输入的数据量相同的空间(数量级)