我当时写了个算法是o(n)的最坏情况时o(3n)的空间复杂度最坏情况是开个2^21大的数组
感觉楼主的方法不太可行，首先10G个数是不可能存的下来的，
o(n)的空间复杂度也不可以，何况楼主的算法最坏情况时o(n^2)估计几天也算不出来。
其次因该至少要对数据遍历一次的，除非用概率算法求出估计中位数，否则o(logn)的算法是
不存在的。。。。。


[ 此贴被lyly在2007-04-22 15:25重新编辑 ]

郁闷，第一题Joseph觉得简单直接就写了，写完之后又添加了些小的细节东西，还有想使自己的程序效率风格更好些，所以该了好多，估计很乱郁闷了。。。。。。

第一题是5，6，10吗？？感觉好悬阿？？

Quote:

引用第15楼lyly于2007-04-22 15:02发表的:
我当时写了个算法是o(n)的最坏情况时o(3n)的空间复杂度最坏情况是开个2^21大的数组
感觉楼主的方法不太可行，首先10G个数是不可能存的下来的，
o(1)的空间复杂度也不可以，何况楼主的算法最坏情况时o(n^2)估计几天也算不出来。
其次因该至少要对数据遍历一次的，除非用概率算法求出估计中位数，否则o(logn)的算法是
不存在的。。。。。

通过对select算法的改进，已经得到了时间复杂度最坏情况O(n)的了~~空间复杂度O(1)~~~
要不要我放代码？

Quote:

引用第18楼zc1984于2007-04-22 15:22发表的:


通过对select算法的改进，已经得到了时间复杂度最坏情况O(n)的了~~空间复杂度O(1)~~~
要不要我放代码？

蝈蝈发出来吧

楼主的算法没有看懂，不过如果是o(1)的空间复杂度，且是o(n)的时间复杂度
我就挺佩服的了，算法导论上也有o(n)的算法，不过当时没想到那个算法，只好自己想了，
不过感觉自己的方法应该没有问题，最坏只要遍历三次，不用交换数据。
不过o(n)的时间复杂度常系数必须要小，因为计算机每秒只能处理10^8次对于10G的数据
执行一边就需要1分钟所以有些o(n)的算法也不可取哈

Quote:

引用第20楼lyly于2007-04-22 15:44发表的:
楼主的算法没有看懂，不过如果是o(1)的空间复杂度，且是o(n)的时间复杂度
我就挺佩服的了，算法导论上也有o(n)的算法，不过当时没想到那个算法，只好自己想了，
不过感觉自己的方法应该没有问题，最坏只要遍历三次，不用交换数据。
不过o(n)的时间复杂度常系数必须要小，因为计算机每秒只能处理10^8次对于10G的数据
执行一边就需要1分钟所以有些o(n)的算法也不可取哈

就是算法导论上面的那个select算法啊~~~只不过使用改进后的select算法可以把最差的效率提升到O(n)而已~~

现在的处理器是10亿/秒级别的~~~例如我的机器Athlon64 3200+~~对应3200MHz的Pentium4的水平~~
（存在假设：一个时钟周期执行一条简单指令，利用流水线技术等优化措施~）

1分钟处理10G数据，瓶颈不在CPU，而在于硬盘~~你看一下数据传输速度就知道了~~现在的单个硬盘也就60MB/s~
只有使用SAN或者RAID技术~~


[ 此贴被zc1984在2007-04-22 15:52重新编辑 ]

Quote:

引用第21楼zc1984于2007-04-22 15:46发表的:


就是算法导论上面的那个select算法啊~~~只不过使用改进后的select算法可以把最差的效率提升到O(n)而已~~

现在的处理器是10亿/秒级别的~~~例如我的机器Athlon64 3200+~~对应3200MHz的Pentium4的水平~~
.......

对现在计算机技术不是很清楚哈，反正我们做acm题目的时候，如果达到10^8的次数，一秒的时限就会超时(不牵扯到文件读取速度的问题哈).

Quote:

引用第22楼lyly于2007-04-22 15:56发表的:

对现在计算机技术不是很清楚哈，反正我们做acm题目的时候，如果达到10^8的次数，一秒的时限就会超时(不牵扯到文件读取速度的问题哈).

蝈蝈不错哈！！
但是关注现实的实现可能更具有意义~~毕竟ACM里面的东西都来源于实际问题，同样的，也会最终回到实际问题中~

p.s.有没有蝈蝈使用OpenMP之类的东西写并行算法参加ACM的啊？
p.s.2 如果我提交病毒源代码上去，ACM的服务器会怎么样啊？

Quote:

引用第23楼zc1984于2007-04-22 15:59发表的:


蝈蝈不错哈！！
但是关注现实的实现可能更具有意义~~毕竟ACM里面的东西都来源于实际问题，同样的，也会最终回到实际问题中~

.......

没有用并行方法写的，
如果你提交病毒上去，编译器会识别不会予以处理，并且如果是比赛的时候你就挂了，取消比赛资格

现在该研究并行算法了。。这个才是王道

个人觉得，acm都是打题海战的，没有多大意思，就是现有算法的组合，要真正研究算法，还是去研究数学，因为是题海战，这就是中国的ACM成绩通常比较好的原因，但是看现在的计算机行业，欧美领先中国不知道多少年。。。

Quote:

引用第24楼lyly于2007-04-22 16:02发表的:

没有用并行方法写的，
如果你提交病毒上去，编译器会识别不会予以处理，并且如果是比赛的时候你就挂了，取消比赛资格

编译器识别？貌似不可能~~~
有杀毒软件倒是可能，但是这可以预防未知病毒吗？怀疑~~

并行是未来的趋势，不知道什么时候ACM跟上这个趋势~~
现在双内核都不新鲜了，都开始叫卖4内核了~~
IBM Cell都已经是9核心了~~

而且ACM的题目多试基于随机存储的体系的，如果是磁带机？网络流？How？

算法啊~~很有趣的东西~~~被朱清新教成那样~~

以后还是扎实下基本算法和数据结构感觉公司就只考这东西，，，
本感觉自己的项目经验有些优势，但是关于软件开发和vc一点都没涉及。。。

Quote:

引用第27楼zc1984于2007-04-22 16:08发表的:


编译器识别？貌似不可能~~~
有杀毒软件倒是可能，但是这可以预防未知病毒吗？怀疑~~

.......

编译器限制了你可以使用的库函数，以及可以调用的资源，并在超过规定时间后强行停止运行。。。。所以想用病毒攻击，是比较麻烦的事哈