该笔记整理自七月在线网（https://www.julyedu.com ）的算法视频课程
一、介绍
算法很重要，是解决问题的步骤，具有有穷性，确定性、可行性、输入输出。
面试时面试官看重的是解决问题的能力，从暴力解法改良到高效解法。即使不能一下子想到最优算法，也要有自己想法，然后一步步优化去冗余步骤（下面会用一道例题体现这个过程）。
二、复杂度
常用大O表示法。
时间：基本操作次数（汇编指令条数）
空间：占用内存字节数
区别：空间可再利用
常见时间复杂度分析方法 ：
- 数循环次数
- 均摊分析
- 递归式——主定理
基本运算如+-*/：O（1）
问题规模可按分数减小，如二分查找：O（logn）
线性查找：O（n）
朴素最近点对，选择排序：O（n²）
Floyd，普通矩阵乘法：O（n³）
O（nlogn），快排期望复杂度，一般为归并排序，堆排序以及相关的，也是基于比较排序的算法下界。
总结：
优秀：O（1）<O(logn)<O(n)<O(nlogn) 面试时当复杂度是这些时一般就不用再优化了
可能需要继续优化：O(n²)<O(n³)<O(n!)
三、分治法主定理（只是一个公式，面试一般不考，了解即可）
递归式与分治方法是紧密相关的，因为使用递归式可以清晰的刻画分治算法的运行时间。
主方法如下：
T(n) = aT(n/b) + f(n)
a>=1 b>1 f(n) 是给定的函数。这种形式的递归式很常见。刻画了一个分治算法。生成a个子问题。每个子问题是原来的1/b。分解和合并步骤共消耗f(n)
主方法是计算时间复杂度的时候用的。
利用上面的这个定理就可以计算递归式的时间复杂度了，这里面的1）与3）换句话说就是1)f(n)nlogb^a
T（n） = 9T(n/3) + n 那么计算其渐进界就是nlog39=n2
四、均摊法
多个操作一起算复杂度，再除操作次数得每次操作复杂度。基本理念是，给定一连串操作，大部分的操作是非常廉价的，有极少的操作可能非常昂贵，因此一个标准的最坏分析可能过于消极了。因此，其基本理念在于，当昂贵的操作特别少的时候，他们的成本可能会均摊到所有的操作上。
五、例题
leetcode 53. Maximum Subarray 注意思考优化问题复杂度，去除冗余步骤的过程
题目： 给定数组a[1…n]，求最大子数组和，即找出1<=i<=j<=n， 使a[i]+a[i+1]+…+a[j]最大
PS：建议直接在leetcode上写代码，培养好代码习惯，训练徒手写代码能力。
1.暴力枚举O（n³）
首先可以想到用二重循环
public class Solution {
public int maxSubArray(int[] nums) {
int max=nums[0];
int n = nums.length;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
int result = 0;
for(int k=i;k<=j;k++){
result=result+nums[k];
}
if(result>max)
max=result;
}
}
return max;
}
}
提交后发现超时，（面试时拿到问题如果没有好的想法可以先讲一下暴力解法，比较差的算法面试官也可以接受，一定要有思路。面试官一定会继续问能不能优化，接下来继续思考有没有冗余的步骤可以去掉）
2.优化枚举，二重循环
思考上述过程是否有冗余步骤：计算过子数组A的和后，想计算子数组AB的和，可以像上面一样找到AB，循环累加AB，但是计算A的和的过程重复了。可以直接在A的和基础上继续累加B。
时间复杂度 O(n2) 附加空间复杂度 O(1)
public class Solution {
public int maxSubArray(int[] nums) {
int max=nums[0];
int n = nums.length;
for(int i=0;i<n;i++){
int result = 0;
for(int j=i;j<n;j++){
result=result+nums[j];
if(result>max)
max=result;
}
}
return max;
}
}
虽然复杂度降低，但提交后依然超时。
3.贪心法，一重循环，O（n）
此时面试官应该会继续提醒你优化。继续思考，刚刚我们找了所有的子数组及其累加和，方法2也只是优化了累加部分，令循环累加O（n）变成O（1）。但各子数组是有重叠的，如下图，
当发现子数组A的和小于零时，其实我们就不用计算子数组AB的和了，直接计算B即可，因为A的和小于零，AB一定小于B，也就是所有以A为前缀的子数组都不用计算了。换言之，只有当A的和>0时，A才会对子数组累加结果增长有帮助。
贪心法可以理解为只要对自己好的，对自己不利的一律不要。若A<0,它对后面子数组求和结果的贡献一定是负的，所以不要，若A>0,A的贡献是正的（可以令子数组和变更大），要它。不要小于零的，只要大于零的。由此想到下面算法。
时间复杂度 O(n) 附加空间复杂度 O(1)。
累加子数组，当发现sum小于零时，令sum=0（丢弃前面的累加和，继续计算后面的和，也就是当发现前面的A的sum为零时，跳过A为前缀的子数组，直接计算A后面的和），丢弃之前已经把前面的最大子数组和保存在ans里，不用担心最大子数组和出现在前面怎么办（每次计算sum后都比较更新ans）。
public class Solution {
public int maxSubArray(int[] nums) {
int max=nums[0];
int n = nums.length;
int sum = 0;
for(int i=0;i<n;i++){
sum+=nums[i];
if(sum>max)
max=sum;
if(sum<0){
sum=0;
}
}
return max;
}
}
AC！
时间复杂度O（n），此时如果面试官还问可不可以优化时，我们就可以自信的说，这应该已经是最优解了😁
这道题很经典，理解拿到一个问题给出一个解然后逐步优化的思想。
PS：在算法优化中还有一种用空间换时间的想法，类似桶排序那种思路，现在暂时想不到例题，这篇笔记就不写了，以后遇到类似问题再总结。
网友评论