还是1000个数找100个最大的。

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2010-11-27 字数 113

额外开辟的空间不得大于1200*sizeof(int),要求在最坏情况下,比较次数小于3000。

咋做?貌似我只会平均比较次数小于3000。

Algorithm 算法
16 个回复
dothegame
dothegame 2010-11-28

用个数组,a[100],遍历一遍1000个数,往数组里填充,填的时候排序一下。

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 额外开辟的空间不得大于1200*sizeof(int),要求在最坏情况下,比较次数小于3000。

: 咋做?貌似我只会平均比较次数小于3000。

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2010-11-28

比较次数是多少?

【 在 dothegame () 的大作中提到: 】

: 用个数组,a[100],遍历一遍1000个数,往数组里填充,填的时候排序一下。

Ronnielee
R9 2010-11-28

用个最小堆

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 额外开辟的空间不得大于1200*sizeof(int),要求在最坏情况下,比较次数小于3000。

: 咋做?貌似我只会平均比较次数小于3000。

dothegame
dothegame 2010-11-28

不知道多少次,不过似乎少于3000次是一定的。

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 比较次数是多少?

Ronnielee
R9 2010-11-28

期望小于还是最坏情况小于?

【 在 dothegame () 的大作中提到: 】

: 不知道多少次,不过似乎少于3000次是一定的。

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2010-11-28

能证明么?

【 在 dothegame () 的大作中提到: 】

: 不知道多少次,不过似乎少于3000次是一定的。

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2010-11-28

最小堆只能保证平均比较次数在3000左右。不能保证最坏情况小于吧?

【 在 Ronnielee (R9) 的大作中提到: 】

: 用个最小堆

dothegame
dothegame 2010-11-28

这还要啥证明。 估算一下就知道了 我再想用堆好些还是二叉搜索树好些。

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 能证明么?

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2010-11-28

那请你估算一下是多少吧。

【 在 dothegame () 的大作中提到: 】

: 这还要啥证明。 估算一下就知道了 我再想用堆好些还是二叉搜索树好些。

dothegame
dothegame 2010-11-28

给你个程序,能给我点工钱不?

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 那请你估算一下是多少吧。

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2010-11-28

证明你的能力先。

这都什么时代了,还空口说白话。

【 在 dothegame () 的大作中提到: 】

: 给你个程序,能给我点工钱不?

dothegame
dothegame 2010-11-28

不给钱谁给你干活啊 有病。

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 证明你的能力先。

: 这都什么时代了,还空口说白话。

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2010-11-28

慢走。

【 在 dothegame () 的大作中提到: 】

: 不给钱谁给你干活啊 有病。

wxstorm
企鹅 2010-11-28

一个排序序列

1000,999.....1

你用100的数组试试,比较小于3K?

【 在 dothegame () 的大作中提到: 】

: 这还要啥证明。 估算一下就知道了 我再想用堆好些还是二叉搜索树好些。

dothegame
dothegame 2010-11-28

肯定要比这个全排列快。

比较次数小于3000,我不知道要怎样变态才会有这样的要求。

【 在 wxstorm (企鹅) 的大作中提到: 】

: 一个排序序列

: 1000,999.....1

: 你用100的数组试试,比较小于3K?

wxstorm
企鹅 2010-11-28

不全排列,那100算你排好序,放入8个之后,接下来放入的任何一个比较次数都至少是3。

很快过3k了

【 在 dothegame () 的大作中提到: 】

: 肯定要比这个全排列快。

: 比较次数小于3000,我不知道要怎样变态才会有这样的要求。