一亩三分地论坛

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

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

[CS 61B Spring 2015] Homework 6

[复制链接] |试试Instant~ |关注本帖
HNAKXR 发表于 2016-2-21 13:02:37 | 显示全部楼层 |阅读模式

[其他]CS 61B: Data Structures #9 - 2015-01-01@UC Berkeley

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

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

x
本次hw的内容是写一个BSTMap(其实就是模仿),运行速度测试,等等。
 楼主| HNAKXR 发表于 2016-2-21 13:03:25 | 显示全部楼层
1: BSTMap - Map61B Round Two!

2: So... How Fast Is It?
InsertRandomSpeedTest
L        n        ULLMap        BSTMap        TreeMap
10        5000        0.14        0.01        0.01
10        10000        0.49        0.01        0.01
10         15000        1.10        0.01        0.01
10        20000        2.14        0.02        0.03

InsertInOrderSpeedTest
n        ULLMap        BSTMap        TreeMap
5000        0.25        0.28        0.02
10000        1.15        1.04        0.02
15000        3.04        2.54        0.01
20000        3.42        4.14        0.02

3 Asymptotics: Put On Your Thinking Cap
1 F For inserting a sorted array in order, the worst runtime is N rather than log N.
2 F Same reason, consider the worst case.
3 F It can be much faster (log N) for random insertion.
4 T It can't be worse than the worst case N.
5 T N^2 > N > log N for large N.
6 T They are designed using the same divide-and-conquer approach.
7 F Best case can be constant.
8 O(N log N): numberOfNodes is O(N) while the mystery itself is O(log N).

4: Mehrheit Für Die Mitleid

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 17:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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