在接触算法之初, 我为诸如快速排序, 二分查找效率感到惊讶.
随着代码量的增加, 对于如动态规划之类以空间换取时间的算法, 我还能理解. 但是我始终不明白如二分查找这类需要前置条件算法为什么能提高程序效率, 虽然查找快了, 但是开销浪费在了排序上, 使用二分查找的一次读写的开销和, 甚至很可能比不使用算法还要慢.
最近在阅读了一些开源代码之后, 终于有点明白为什么如二分查找这类需要前置条件算法可以提高程序效率了.
在程序设计中, 使用如二分查找这类需要前置条件的算法之所以能够提高效率, 并非是他能够降低所有操作的开销, 而是他可以将某种频繁操作的开销转嫁一部分到生成前置条件的不频繁操作上去.
以二分查找为例, 写入数据时的排序带来的开销, 其实就是在查找数据时使用二分查找所降低的开销转嫁过来的, 当然排序所带来的开销可能会略大于查找所带来的开销.
如果对于一块数据的查询频率远大于其更新速度, 查找操作所省下来的开销, 将远大于写入数据时排序所带来的开销, 那么整个程序对于这块数据的查找, 更新的开销和, 将远小于不使用算法的开销和. 这是一个很容易算的小学数学题:D
相反如果数据的更新频率远大于查询频率, 还硬要去使用二分查找, 那么整个程序对于这块数据的开销要远大于直接暴力查询.
因此算法的使用一定要根据具体情况进行分析, 不然高效的算法也可能会拖慢程序的速度.