常见的优化算法

优化一：预处理优化

预处理优化之——前缀和优化：

非常常见的优化方式。此处的前缀和指某数组的前i项和。

如给定数组a[n]，求sum[n]。其中sum[i]=a[0]+a[1]+...+a[i]

这里的sum[]数组即为数组a的前缀和数组。

那么前缀和有什么用处呢？

假设我要求a[x]+a[x+1]+a[x+2]+...+a[y]

那么这个答案就等于 sum[y]-sum[x-1](x!=0)。若x=0则等于sum[y]。

这样的话，能够有效的减少程序中重复计算的次数

有一点：如果原数组的数字是非负的，那么sum数组则是非递减的，在搜索的时候可以考虑使用二分。

其他预处理优化。

预处理根据题目需要求的问题，事先处理好保存起来，解决问题的时候可能需要多次使用，这样的话，只需要计算一遍，不用每次需要用的时候重复计算。

优化二：离线处理

解决问题时可能会需要很多问题的答案，而这些问题是无序的。但是假如这些问题是有序的，可以一次性直接处理出结果。那么我们可以先将询问排序，然后一次性处理出所有结果，然后再将结果按照询问的顺序给出。

总的来说，离线处理即预先保存好所有询问，然后一次性给出所有结果。

当然这么做的前提是能提高效率。

其他优化：

例如

1.二分查找。

在查找的区间比较大的时候，应考虑二分查找以减少算法的时间复杂度。但要注意的是：是在升序数组还是在降序数组进行二分查找，这两种情形是不同的，在做题目的时候应该注意到这个问题

2.用快速排序代替冒泡或者选择排序

很多时候我们要用到对数据排序的时候，往往会选择用快速排序。这样做的话也是提高程序效率的一种方法，毕竟在大量数据的情况下，快速排序运算的速度比常规排序好很多。

通常我们手写快排或者运用C++stl中内置的优化后的sort或者qsort快排

如有错误，还请指正，O(∩_∩)O谢谢