一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 417|回复: 3
收起左侧

[算法题] leetcode 108, 109

[复制链接] |试试Instant~ |关注本帖
wxl3691 发表于 2016-8-15 04:10:23 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
最近再刷题,看了不少题解,都说108 Convert Sorted Array to Binary Search Tree 的时间复杂度是O(n), 但二分应该是O(logn).
而Convert Sorted List to Binary Search Tree的时间复杂度却是O(nlogn)。
这说不通啊,谁能解释听听,是不是书写错了?
窗外一棵树 发表于 2016-8-15 05:37:20 | 显示全部楼层
书上是对的。 108里面,因为是array,所以你可以用O(1)的时间找到一个数组中间的元素,总体的复杂度等于只遍历了一遍数组,所以是O(n).
对109来说,如果你还想用108的方法做,那每次recursion时需要花O(n/2)的时间找到中间元素,这是由linked list的性质决定的。
所以你可以由此想到肯定不是O(n)了。
至于为什么是O(nlgn):  T(n) = n/2 + 2T(n/2), 推导一下这个公式就能得出结论了。
回复 支持 1 反对 0

使用道具 举报

 楼主| wxl3691 发表于 2016-8-15 04:33:51 | 显示全部楼层
Convert Sorted List to Binary Search Tree 我说的不是最优解,是top-down的解法
回复 支持 反对

使用道具 举报

 楼主| wxl3691 发表于 2016-8-15 07:23:32 | 显示全部楼层
窗外一棵树 发表于 2016-8-15 05:37
书上是对的。 108里面,因为是array,所以你可以用O(1)的时间找到一个数组中间的元素,总体的复杂度等于只 ...

明白了,感谢
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 06:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表