作者st474ddr (hikke)
看板Grad-ProbAsk
标题[理工] 103成大 程式设计
时间Sat Jan 19 23:04:57 2019
https://i.imgur.com/VwTE6qR.jpg
小弟要问一下是非第三题的答案
我不是很确定worst case用chain能不能到O(log n)
https://i.imgur.com/q2m1gHX.jpg
演算法是非2、3小题
不确定答案 我都不知道怎麽解释
第3小题之前板上有
只是我不太懂
还有第二大题 他有两个条件
这要怎麽去算他的时间复杂度啊
谢谢各位大大
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.9.14.160
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1547910299.A.738.html
1F：推 yp195126: 1.3 F 如果每个数都对应到同一格 这样chain长度为n 最长 01/19 23:48
2F：→ yp195126: 搜寻时间为O(n) 01/19 23:48
3F：推 yp195126: 演算法1.2 如果是skew-tree 需要O(n) 可以画图实作看看 01/19 23:52
4F：→ yp195126: 演算法1.3 merge A1A2A3成一个sort list需要O(n+n+n)=O( 01/20 00:22
5F：→ yp195126: n) 因为是balance bst 所以root需为中间值 在list找到中 01/20 00:22
6F：→ yp195126: 间值的时间为O(1) 用递回概念 T(n)=2T(n/2)+O(1)=O(n) 01/20 00:22
7F：→ yp195126: 两者相加为O(n) 01/20 00:22
8F：→ dumpling1234: 想问ㄧ下第三题 如果list用AVL tree去maintain的话 01/20 00:38
9F：→ dumpling1234: 不是可以达到O(logn)吗? 01/20 00:39
10F：→ yp195126: logn是单项操作的时间吧 要再乘上n 因为题目给的是low b 01/20 00:46
11F：→ yp195126: ound 但有办法在小於O(nlogn)的时间求出 01/20 00:46
12F：→ yp195126: 所以答案是F 01/20 00:48
13F：→ dumpling1234: 我说的是DS Hash 那题 01/20 01:09
14F：推 yp195126: Chaining mouther是以link list的方式去串联同一格的值 01/20 01:15
15F：→ yp195126: 搜寻时间比照link list 01/20 01:15
16F：→ yp195126: 是chaining method...选错字 01/20 01:15
18F：推 moriahyen: 想同问M是什麽?? 常数吗?? 01/20 10:12
19F：→ st474ddr: 感谢大大们 01/20 11:24
20F：→ alen0303: 关於那个M 台大考过类似题 是当变数来看 01/20 14:18