讨论一个算法

lenovo

原帖由 知道什么叫滚么 于 2007-3-20 17:16 发表


设置一个单调增长的hash函数不就可以排序了么？

有你这样的hash函数么？

flw

原帖由 知道什么叫滚么 于 2007-3-20 17:16 发表

设置一个单调增长的hash函数不就可以排序了么？

那是 key 排序，不是 value 排序。

flw

原帖由 lenovo 于 2007-3-20 17:13 发表

我觉得3楼给出的那个算法就可以，
不知道你们怎么看？

那段代码不咋的。问题有三：
1，极度零乱（这也是我没有仔细看的原因之一，另一个原因就是我从数学上认为楼主的需求是不可能的，不过既然你这么说，我还是仔细看了一遍他的代码）
2，sizeof 那一句写法是错误的。正确的计算数组元素个数的方法是（通用）：
# define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))，他那个移位来移位去的做法是错误的。
3，他的核心思想仍然是用了 hash 的思想。而且用的是一种很简单的 hash 算法：将 int 值作为 hash 的 key。这个算法要求一个尺寸为 2^32 次方的元素个数的 hash，可惜他分配的 count 数组远远小于这个大小。

lenovo

原帖由 flw 于 2007-3-20 17:29 发表

那段代码不咋的。问题有三：
1，极度零乱（这也是我没有仔细看的原因之一，另一个原因就是我从数学上认为楼主的需求是不可能的，不过既然你这么说，我还是仔细看了一遍他的代码）
2，sizeof 那一句写法是错误 ...

看来O(n)是不可能了。

cobras

最少需求是2^(32-3)=2^29字节=512MB
所以n只能是有限集

flw

原帖由 lenovo 于 2007-3-20 17:32 发表

看来O(n)是不可能了。

所以要化不可能为可能嘛。
如果这些数据本身就是不可控的熵度极高的数据，那么自然是没有办法的。
但是如果这些数据本来就是由别的程序生成的，而且别的程序怎么生成都行，那么只需要改改生成数据的程序，让它放的时候就放整齐一点，那么就可以实现 O(n) 甚至是 O(1) 的算法。

lenovo

原帖由 flw 于 2007-3-20 17:37 发表

所以要化不可能为可能嘛。
如果这些数据本身就是不可控的熵度极高的数据，那么自然是没有办法的。
但是如果这些数据本来就是由别的程序生成的，而且别的程序怎么生成都行，那么只需要改改生成数据的程序，那么 ...

刚才想了想，能不能找到这个问题的O（n）的算法，
最后可以归结到能不能找到O（n）的排序算法。
像基数排序，此外还有桶、箱排序都是O（n）的，
但它们都有一些限制。

soul_of_moon

我好像记得在学数据结构时，复杂度分最小、最大和平均三种

A.com

顺序读取整数并根据其值放入数组（n，n），当读取的整数其位置已被占用时，相同值就找出来了。

uclinux_arm9

原帖由 uclinux_arm9 于 2007-3-17 15:46 发表
#include<stdio.h>
main()
{
int a[] = {1,2,3,4,5,5,6,7,8,9,10};
const int len=sizeof(a)>>(sizeof(int)>>1);
int count[sizeof(a)>>(sizeof(int)>>1)]={0};
register int idx=0;
int nResult=-1;
for(idx=0;idx<len;idx++)
  {  if( ++count[a[idx]]>1){nResult=idx;break;};
}
printf("index=%d        a[%d]=%d\n",nResult,nResult,a[nResult]);
}

上机测试一下　这个是答案