Welcome To Ask or Share your Answers For Others

匈牙利算法的时间复杂度问题

asked Jan 27, 2021 in Technique[技术] by 深蓝 (71.8m points)

匈牙利算法用链表时间复杂度是O(M+N)？
不是O(N^3)吗，还是说链表通过处理可以优化匈牙利算法
有人能解释下不？

与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…

372 views

Welcome To Ask or Share your Answers For Others

1 Answer

answered Jan 27, 2021 by 深蓝 (71.8m points)

写得好复杂度是O(M*N)没有问题

但是如果用dfs的话常数项会很大，容易被卡常

与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…

...