算法分析一般步骤算法

很多程序员都爱犯的一个毛病，就是刚开始动手写代码就想找到最优解，对那些已经被人解决过的问题，还可以通过网络获取最优化的解决方案，当进入一个全新的领域，这种想毕其功于一役的想法会限制人的能力，推迟项目进度。
【算法分析一般步骤】更一般的做法是：
1)先分析问题，找到一个可行的方案
2)将方案落地
3)思考当问题规模增大一个量级（10倍）时，这套方案能在可接受的时间内给出问题答案吗
4）如果随着问题规模不断增长，方案不能在期望时间内给出问题答案，我们就要分析，那一块儿出现了性能瓶颈，优化它
5) 就这样不断优化方案，直到处理能力达到数学规定的上界，就有了最优解
来看一个twoSum问题：
输入一个数组，找出数组中和为0的数字对之和。
先给出一个简单的方案：使用暴力枚举法，粗犷，但是能解决小规模问题

public class TwoSum {public static int twoSum(int[] arr){ int cnt = 0; for(int i = 0; i < arr.length; i++) for(int j = i + 1; j < arr.length; j++) if(arr[i] + arr[j] == 0) cnt++; return cnt; }public static void main(String[] args) { int[] arr = {1,-1,0,2,-2,3,-3,5,6,7,-7}; System.out.println(TwoSum.twoSum(arr)); } }

这个方案的复杂度是，随着问题规模不断增大，性能会越来越差，难以满足需求，那就想办法将其复杂度降为，即问题转化为将一个n降为。我们知道二分法可以实现这种需求：

public class BinarySearch {public static int rank(int key, int[] arr) { if(arr == null || arr.length == 0) { return -1; } int high = arr.length - 1; int low = 0; while(low <= high) { int mid = low + (high -low)/2; if(arr[mid] == key){ return mid; } if(arr[mid] > key) { high = mid - 1; } if(arr[mid] < key) { low = mid + 1; } } return -1; }public static void main(String[] args) { int[] arr = {1,2,3,4,5,6,7,-1,10,15}; System.out.println(BinarySearch.rank(5, arr)); } }

利用二分法来改进算法：

public class TwoSumFast {public static int twoSumFast(int[] arr){ int cnt = 0; Arrays.sort(arr); for(int i = 0; i < arr.length; i++) { if(BinarySearch.rank(-arr[i], arr) > i) { cnt++; } } return cnt; } public static void main(String[] args) { int[] arr = {1,-1,0,2,-2,3,-3,5,6,7,-7}; System.out.println(TwoSumFast.twoSumFast(arr)); } }

须知，如果a[i] + a[j] = 0,那么a[j] = -a[i],即遍历数组，如果存在-a[i],那么一定存在满足twoSum规则的子数组。
那么还有比这种方案更快的算法吗？数学上可以证明，没有，这是最优解了。
最后，要明白一点：一个能不断演化的算法更有价值，一个能不断成长的人生更有意义！