啊！？ “编程的核心是数据结构,而不是算法”《UNIX编程哲学》里竟然有这句话啊！

star_in_sky

回复 9# pmerofc


    呵呵，在链表（尽管链表已经排过序了）中使用二分法，确实比较雷人（不过不排除实际情况中，这也是一个无奈的选择吧），虽然不能算错误，但至少是不好的。

   不管怎么样，这个例子也是一个鲜活的“反面典型”，相信LZ看了这个例子之后，就会更加明白：正确的数据结构是正确的算法的前提。

   其实，反面例子的说服力更强

shan_ghost

pmerofc 发表于 2013-01-18 11:04
给你个真实的例子   
http://www.cnblogs.com/pmer/archive/2012/12/08/280 ...

喷了………………………………………………………………………………………………………………

shan_ghost

star_in_sky 发表于 2013-01-18 11:17
虽然不能算错误，但至少是不好的。

这就是错误好不好……


在数组上二分搜索，复杂度是O(logN)；在链表上直接挨个搜索，复杂度是O(N)；在链表上二分搜索，复杂度是O(N*logN)，复杂度直接上了半个级别啊喂～～

star_in_sky

回复 13# shan_ghost


    呵呵，不能通过数组ID直接定位元素。

   “错误”更加准确

liuiang

这个问题之前论证过的，问题核心在于：如果比较的开销远远大于遍历的开销，那么，基于链表进行二分法不一定就是错误的选择。算法是死的，人是活的。

不过乔的例子则是错误。

shan_ghost

回复 14# star_in_sky


    以前没注意看……刚才去看了代码……

关于这个N、log(N)、N(log N)的复杂度，我举个直观的栗子吧：

假设这个N是1024，假设CPU做每次操作（找到元素+比较）要1秒，那么逐个比较最坏就要1024秒；而数组上的二分查找最坏只需10秒（2^10=1024）；链表上的二分查找呢，最坏需要10*1024=10240秒。

而且，这三个数字的差距，随着N的增加还会继续增加……


从10秒到一千多秒到一万多秒——现在，明白复杂度上半个台阶是多么不可容忍之事了吧。

shan_ghost

liuiang 发表于 2013-01-18 11:43
这个问题之前论证过的，问题核心在于：如果比较的开销远远大于遍历的开销，那么，基于链表进行二分法不一定 ...

嗯，同意这个说法。

凑十个字……

shan_ghost

liuiang 发表于 2013-01-18 11:43
这个问题之前论证过的，问题核心在于：如果比较的开销远远大于遍历的开销，那么，基于链表进行二分法不一定 ...

不过，一般来说，正确的解决方案应该是调整数据结构而不是写这种诡异的算法吧。

甚至，必须用链表存储的话；还可以学数据库，另外建一个数组来索引链表中的每个node；查找可以直接在数组上进行——数据结构是死的，人是活的。

liuiang

回复 18# shan_ghost


    那是当然，这种应用基本上很少有。

liuiang

回复 18# shan_ghost


    这只是针对专家经常一棍子打死这个一棍子打死那个，而提出来的反例，实际应用场景几乎为0.