楼主:
st474ddr (hikke)
2019-01-19 23:04:57https://i.imgur.com/VwTE6qR.jpg
小弟要问一下是非第三题的答案
我不是很确定worst case用chain能不能到O(log n)
https://i.imgur.com/q2m1gHX.jpg
算法是非2、3小题
不确定答案 我都不知道怎么解释
第3小题之前板上有
只是我不太懂
还有第二大题 他有两个条件
这要怎么去算他的时间复杂度啊
谢谢各位大大
作者:
yp195126 (我睡故我在)
2019-01-19 23:48:001.3 F 如果每个数都对应到同一格 这样chain长度为n 最长搜寻时间为O(n)算法1.2 如果是skew-tree 需要O(n) 可以画图实作看看算法1.3 merge A1A2A3成一个sort list需要O(n+n+n)=O(n) 因为是balance bst 所以root需为中间值 在list找到中间值的时间为O(1) 用递回概念 T(n)=2T(n/2)+O(1)=O(n)两者相加为O(n)
想问ㄧ下第三题 如果list用AVL tree去maintain的话不是可以达到O(logn)吗?
作者:
yp195126 (我睡故我在)
2019-01-20 00:46:00logn是单项操作的时间吧 要再乘上n 因为题目给的是low bound 但有办法在小于O(nlogn)的时间求出所以答案是F
作者:
yp195126 (我睡故我在)
2019-01-20 01:15:00Chaining mouther是以link list的方式去串联同一格的值搜寻时间比照link list是chaining method...选错字
楼主:
st474ddr (hikke)
2019-01-20 11:24:00感谢大大们
作者:
alen0303 (艾伦零参 智商负三)
2019-01-20 14:18:00关于那个M 台大考过类似题 是当变量来看