求一取最大值得算法！！常见排序算法不要。

windoze

回复 25# cxytz01


这个需求…………
其实和数组半毛钱关系都没有，表用select就好了，改用epoll/kqueue/....啥的就不用纠结了

windoze

回复 30# cxytz01

在n个数字中找最大值，O(n)是理论上限，表想了。
不信可以找个搞数学的证明一下

windoze

回复 33# cxytz01

对你的场景一点用没有，n个数字建堆需要O(n long(n))复杂度，还不如O(n)

windoze

回复 49# folklore
所以你的方案就变成了两个步骤，第一要确定数据是否有序，第二才是取最大值。
第一个步骤需要n log(n)

windoze

yulihua49 发表于 2013-01-10 19:47
完全不用任何的序。在accept后判定fd的最大值即可：

对于总共n个连接，难道那个循环不用执行n次？

windoze

回复 55# yulihua49

原来只要“忽略不计”，复杂度就可以变成O(0)的，楼上的高度果然有好几十层楼那么高……
干脆以后就表优化神马程序了，反正对于宇宙几十亿年漫长的寿命而言，程序执行的那点时间都可以忽略不计的

windoze

star_in_sky 发表于 2013-01-10 21:59
回复 49# folklore
建堆的复杂度是O(n)。

这个不就是O(n)了？还能更快么？

windoze

cxytz01 发表于 2013-01-10 22:46
现在想做的，既不是epoll，也不是多进线程，而是将单线程的功能最大化！

epoll不就是将单线程功能最大化的方法么？不明白楼主为什么抱着select/poll不放

man page第一句话就是：
epoll is a variant of poll...

简单说，epoll就是一个不用每个连接都把maxfd重新弄一遍的select/poll

windoze

回复 69# yulihua49

找最大数当然是O(n)，这个是理论上限。
但是lz提错了需求，他说他就要让select/找maxfd更快点，可是早就有人告诉他，epoll/devpoll/eventport/kqueue/IOCP就是更快的select，而且不需要找maxfd。

复杂度就是复杂度，不是你“忽略掉”就不存在的，只有不需要做的事复杂度才是0。