很多程序员都爱犯的一个毛病，就是刚开始动手写代码就想找到最优解，对那些已经被人解决过的问题，还可以通过网络获取最优化的解决方案，当进入一个全新的领域，这种想毕其功于一役的想法会限制人的能力，推迟项目进度。
更一般的做法是：
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规则的子数组。
那么还有比这种防范更快的算法吗？数学上可以证明，没有，这是最优解了。
最后，要明白一点：一个能不断演化的算法更有价值，一个能不断成长的人生更有意义！
网友评论