|
锁定老帖子 主题：最长平台的新算法
精华帖 (0) :: 良好帖 (2) :: 新手帖 (2) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-04-29
Heart.X.Raid 写道 LZ 你的改进党的算法有很大问题：
测试一下这组数据吧： 1,1,1,2,2,3,3,3,3 经典算法确实有一些“比较”次数感觉上是没有必要的，但是不能根据当前的length就认定下一次的平台一定可以越过length的长度不参与比较。 就比如上面的例子，1,1,1说明length=3，你认为后面的平台可以越过3次比较吗，也就是next=4--next=6这三个数都可以丢弃吗，注意你丢弃了2,2,3, 本来4个3的平台你丢掉了一个。 我最开始觉得优化确实可以跳跃，但是后来发现，跳跃多少不是一个简单的问题。这和每个平台最开始的分界点有关。 并没有丢弃2,2,3，跳到的地方，是两个3之间，所以不是分界点，所以会计算改点所在的平台。 |
| 返回顶楼 | |
|
发表时间：2010-04-30
可是我用1,1,1,2,2,3,3,3,3 这组数据测试你的程序，结果是错误的，显示最大平台长度为3，而不是4(3,3,3,3)。
|
| 返回顶楼 | |
|
发表时间：2010-05-01
我知道你程序的意思了，逻辑上应该没有问题。效率上确实有提高，但是应该存在最坏的可能性，我觉得当平台的大小基本正序(从大到小)的时候，效率最高，如果逆序过多，则每次跳跃之后基本上都需要回头向前遍历。则效率会大打折扣
|
| 返回顶楼 | |
|
发表时间：2010-05-01
Heart.X.Raid 写道 可是我用1,1,1,2,2,3,3,3,3 这组数据测试你的程序，结果是错误的，显示最大平台长度为3，而不是4(3,3,3,3)。
我运行的结果是4. |
| 返回顶楼 | |
|
发表时间：2010-05-02
对不起 是我搞错了。程序没有错，效率应该是有改进的，但是有最差情况。
|
| 返回顶楼 | |
|
发表时间：2010-05-02
最后修改：2010-05-02
其实， 我觉得可以用lg(n)的复杂度求解的。 因为这是个有序的数列， 根据信息论原理， 查找他的复杂度就是lg(n). 但是， 我想不出怎么用lg(n)解法。 最简单的优化就是基于递归的解法： f(x+1) = f(x)+ n x表示当前最大长度。 这样程序上， 就可以越过之前检查过的长度。
这问题怎么跟求最大子序列这么象呢。 除了有序。。。 |
| 返回顶楼 | |
|
发表时间：2010-05-03
sdh5724 写道 其实， 我觉得可以用lg(n)的复杂度求解的。 因为这是个有序的数列， 根据信息论原理， 查找他的复杂度就是lg(n). 但是， 我想不出怎么用lg(n)解法。 最简单的优化就是基于递归的解法： f(x+1) = f(x)+ n x表示当前最大长度。 这样程序上， 就可以越过之前检查过的长度。
这问题怎么跟求最大子序列这么象呢。 除了有序。。。 这个理论的依据是什么？ 你的这个递归式子有问题吧。 |
| 返回顶楼 | |
|
发表时间：2010-09-01
zhang_xzhi_xjtu 写道 sdh5724 写道 其实， 我觉得可以用lg(n)的复杂度求解的。 因为这是个有序的数列， 根据信息论原理， 查找他的复杂度就是lg(n). 但是， 我想不出怎么用lg(n)解法。 最简单的优化就是基于递归的解法： f(x+1) = f(x)+ n x表示当前最大长度。 这样程序上， 就可以越过之前检查过的长度。
这问题怎么跟求最大子序列这么象呢。 除了有序。。。 这个理论的依据是什么？ 你的这个递归式子有问题吧。 如果我们用二分法去划分，直到分区内为同一个数(比较头尾)，然后递归上来，O(n)。 对于划分线两边同值的情况，我们需要向两边寻找它的边界，生成多一个递归分支，这样的动作加起来是lg(n)的平方。 这样甚至比简单的遍历还差。 |
| 返回顶楼 | |
