问答

当前位置

邮局的建立问题:时间复杂度

  • by zz
  • 2
  • 1 年,8 月前
  • Ta: 陆助教

http://www.jiuzhang.com/solution/build-post-office-ii/

这个题目有两个解法。

解法一:从每一个empty出发,BFS到所有的house。
解法二:从每一个house出发,BFS到所有的empty。

答案是解法二。为什么呢?是因为前提假设是house比较少,empty比较多吗?

题目的challenge要求找到一个O(n^3)的算法。
我认为BFS的时间复杂度是O(N^2)。为什么遍历house是O(N)呢?是因为房子比较少吗?

2 个回复

2018-02-26 陆助教

为什么呢?是因为前提假设是house比较少,empty比较多吗?
是的,一般不会全部都是房子这样子,所以就从房子出发,如果两者数量是一个级别的,那么算法复杂度就相同
我认为BFS的时间复杂度是O(N^2)。为什么遍历house是O(N)呢?是因为房子比较少吗
准确来讲时间复杂度为O(房子数量 * n * m)


2018-02-28 zz

谢谢陆老师

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1