[CS 61B Spring 2015] Lab 8

Lab 8纯粹是搬砖工作……运行几个程序根据不同的N所需的运行时间，来估算算法的复杂度。

1: Experimentally determining running times
function1: Θ(N^2)
function2: Θ(N)
function3: Θ(N^3)

Experimentally determined running time, assuming runtime is of the form ~aN^b:

function1: ~1.08×〖10〗^(−9) N^2.02
function2: ~1.93×〖10〗^(−9) N^0.95
function3: ~2.18×〖10〗^(−9) N^3.07

2: Match the running time
As expected.

3: Measuring the running times of removing from two data structures
Experimentally determined running time:

ArrayList: 1.15×〖10〗^(−9) N^1.93
HashSet: 1.90×〖10〗^(−6) N^0.96

4: Determining the running time of a sorting algorithm
Experimentally determined running time:

Insertion sort with array: O(N^2.06)
Insertion sort with linked list:  O(N^3.07)

5: Extra practice
Initial guess: O(n√n  )

Experimentally determined running time: O(N^1.50)