问答

当前位置

build post office ii 时间复杂度

  • Ta: 安助教

build post office ii 的时间复杂度是多少呢 http://lintcode.com/en/problem/build-post-office-ii/# 题目描述说challenge是在o(n^3)内结觉,感觉答案用bfs的话只用了o(n^2), 对2d矩阵中每个点跑一遍bfs, 每个bfs是O(n), 所以是O(n^2)? (假设n是矩阵中元素的个数?)

5 个回复

2017-09-21 马同学

bfs是O(n^2)的复杂度,并不是2d矩阵中每个点都要跑一遍bfs,只需有house位置跑即可。可能这里另外一个n指代的是house的个数?


2017-09-21 D同学

why bfs is o(n^2)? i thought each of the n element entets and leaves the queue once in a while loop, which gives us o(n)time complexity?something went wrong with my phone, can only type eng.


2017-09-21 马同学

假设matrix的边长为n,则一共有n^2个元素。


2017-09-21 D同学

got it, that makes sense. so it is o(# of houses * n^2)?

worst case it is o(n^4)when number of houses is o(n^2) level?


2017-09-21 马同学

正确

我来回答

您没有权限

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

登录 注册

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