小编Zom*_*bie的帖子

通常认为A*是解决寻路问题的最佳算法.

当A*不是找到解决方案的最佳算法时,是否存在任何情况？

与BFS,DFS,UCS等相比,A*有多好？

有人可以告诉我解决以下问题的数学部分.

显示没有比较排序,其运行时间至少是n的一半是线性的!长度为n的输入.那么长度为n的输入的1/n的一小部分呢？分数(1 /(2)^ n)怎么样？

解:

如果排序在m个输入排列的线性时间内运行,那么由m个相应叶子和它们的祖先组成的决策树部分的高度h是线性的.使用与定理8.1的证明中相同的参数来表明m = n!/ 2,n!/ n或n!/ 2n是不可能的.我们有2 ^h≥m,这给我们h≥lgm.对于此处给出的所有可能的ms,lgm =Ω(n lg n),因此h =Ω(n lg n).特别是,

    lgn!/2= lg n! ? 1 ? n lg n ? n lg e ? 1
    lgn!/n= lg n! ? lg n ? n lg n ? n lg e ? lg n
    lgn!/2^n= lg n! ? n ? n lg n ? n lg e ? n