Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

大O记号的意义你理解么？

Posted by frkstyc at 2006-06-27 22:39:42 on Problem 1459
In Reply To:做了一个 O(e*log(f)) 的 EK 最大瓶颈增广路算法, 结果效果不好对于这个题目, log(f)应该不大于32, 效率应该很高才对啊 Posted by:semonteer at 2006-06-27 22:38:34

Followed by:

不了解 (0) oeym 2006-06-27 22:41:16
常数的问题, 了解一些 (0) semonteer 2006-06-27 22:42:55
那么也就是说如果规模更大些, 才能体现出优势? 这个算法也称作伪多项式算法么 (0) semonteer 2006-06-27 22:56:41
- 这个很难说的，要让时间达到bound往往需要一些特殊的网络 (0) frkstyc 2006-06-27 23:11:24
您好, 我想了一下, 书上说最多进行log(f)次迭代,f是最终的最大流数值, 每次迭代O(e), 然后对比一下,和我以前的程序相比,常数应该说比较小,我也是用类似prim的贪心法找最大瓶颈路,指点一下吧 (1395) semonteer 2006-06-27 23:16:34
- 我记得capacity scaling是O(E^2lgC)的吧 (1491) frkstyc 2006-06-27 23:27:58
  - 要进行 e*log(c) 次迭代? (0) semonteer 2006-06-27 23:31:26
  - sorry 我错了 (0) semonteer 2006-06-28 00:01:50
    - 为什么这么菜... (0) semonteer 2006-06-28 00:02:06

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator