1.算法复杂度
- 谈算法不谈复杂度=耍流氓
- 在实现之前，我们要预估算法所需要的资源
时间：基本操作次数（汇编指令条数）
空间：占用内存字节数
区别：空间可以再利用
- O(1)
基本运算，＋，－，＊，／，%，寻址 - O(logn)
二分查找 - O(n1/2)
枚举约数 - O(n)
线性查找 - O(n2)
朴素最近点对 - O(n3)
Floyd最短路
普通矩阵乘法 - O(nlogn)
归并排序
快速排序的期望复杂度
基于比较排序的算法下界 - O(2n)
枚举全部的子集 - O(n!)
枚举全排列 - 总结：
优秀 O(1) < O(logn) < O(n1/2) < O(n) < O(nlogn)
可能可以优化 O(n2) < O(n3) < O(2n) < O(n!)
2.从暴力算法开始优化
2.1 Leetcode 121
Best Time to Buy and Sell Stock
2.2 最大子数组和
给定数组a[1…n]，求最大子数组和，即找出1<=i<=j<=n，使a[i]+a[i+1]+…+a[j]最大。
2.2.1 暴力枚举 O(n3)
2.2.2 优化枚举 O(n2)
2.2.3 贪心法 O(n)
2.2.4 总结
3.思考题
3.1 设计一个队列
支持：出队，入队，求最大元素
要求O(1)
均摊分析
3.2 判断是否构成三角形
给定一个正整数组a，是否能以3个数为边长构成三角形？
即是否存在不同的i，j，k，
满足 a[i] < a[j] + a[k]
并且 a[j] < a[i] + a[k]
并且 a[k] < a[i] + a[j]
3.3 Leetcode 152 Maximum Product Subarray
参考
- 1）面试求职 第四期
