一亩三分地论坛

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

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

[CS 61B Spring 2015] Lab 8

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

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

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

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

x
Lab 8纯粹是搬砖工作……运行几个程序根据不同的N所需的运行时间,来估算算法的复杂度。
 楼主| HNAKXR 发表于 2016-2-18 22:19:51 | 显示全部楼层
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)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 05:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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