ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 算法和数据结构

算法和数据结构

原创 Linux操作系统 作者:broadviewbj 时间:2011-08-18 17:03:16 0 删除 编辑

算法和数据结构

算法和数据结构—千丝万缕的联系

纵观各种算法书籍,大多都是将算法和数据结构作为一个整体来讲述。

数据结构就是数组、树结构等存储或表现对象数据的结构。

将算法和数据结构作为整体讲述,是因为必须依照算法中的常用操作选择数据结构。例如,事先将数据保存在适当的树形结构中,大多数情况下搜索会变得很简单,可以降低复杂度。

11课中已经看到,RDBMS的索引的实现采用了B+树这种树结构。B+树是个空间上适合外部存储的树结构。利用B+树保存索引,不仅能减少查找所需的操作步骤,还能将磁盘读取次数降至最低。因此,RDBMS的索引一般采用B+树,同时使用适合该数据结构的算法进行查找、插入、排序等操作。

所以说,算法和数据结构之间存在着千丝万缕的联系。

算法和数据结构

数据结构

数组、树结构、堆……

根据算法常用操作进行选择

要根据算法常用操作来选择数据结构

复杂度和常数项—评测很重要

计算量的复杂度记法忽略了所有“常数项”。所谓常数项就是算法实现中不依赖于输入大小,但却不得不执行的一类处理。

例如函数调用、函数返回等处理都是常数项,第一次分配变量、if语句分支等也是常数项。简单的实现中,常数项几乎不会影响算法的复杂度,但在复杂的实现中,常数项就不可忽略了。就算实现不复杂,CPU缓存是否容易生效、分支预测是否发生等计算机结构特点也会有影响,因此常数项可能会导致差距。

例如,例如排序算法的理论下限为O(n log n),有几个算法的平均复杂度能达到O(n log n)。但是,同为O(n log n),一般而言快速排序是最快的。快速排序的特点使得CPU缓存容易生效,这一点比其他算法好得多。这就是常数项较小的例子。

也就是说,复杂度记法适用于比较算法,但在实现时不应只考虑复杂度。而且常数项经常取决于实现方法,因此实现时要尽力减小常数项。

实现时要注意的优化问题

另一方面希望大家注意,实现某样东西(不仅限于算法)时,一开始就对常数项进行优化,基本上是错误的。努力减少复杂度为O(n2)的算法的常数项,还不如用O(n log n)的算法来代替,那样改善效果更好。

说来说去,还是“评测最重要”。通过评测(benchmark)或分析(profiling)等手段,正确找出当前程序的问题所在最为重要。是要更换算法来改善,还是减少常数项来改善,或者是物理资源不足要更换硬件以改善性能?务必在认真找出问题所在之后,再设法改善。

 

本文节选自《大规模WEB服务开发技术》一书

图书详细信息:http://space.itpub.net/?uid-13164110-action-viewspace-itemid-705176

 

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/13164110/viewspace-705277/,如需转载,请注明出处,否则将追究法律责任。

下一篇: 算法评测
请登录后发表评论 登录
全部评论

注册时间:2008-02-22

  • 博文量
    1030
  • 访问量
    1629769