[CS 61B Spring 2015] Homework 6

本次hw的内容是写一个BSTMap（其实就是模仿），运行速度测试，等等。

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