作者taitin (小南)
看板Grad-ProbAsk
标题[理工] [资结] 98交大资讯联招-DS&algo核对
时间Mon Feb 1 19:42:02 2010
1
(1) -1 -1 0 1 2 0
(2)
10
/ \
2 15
\ \
9 18
/
4
\
7
/
6
(3) 1+2+3+4+6+7+11=34
(图略)
2
(1)
error
foo(b,5,10)
j=5x2
a[j]=a[10] 不存在
(不太晓得..请高手指点)
(2)
n
1/n * Σ(1+(i-1)/b)
i=1
= 1+(n-1)/2b
(3)
0 1 2 3 4
0 0 5 7 ∞ 1
1 ∞ 0 5 ∞ ∞
2 7 5 0 1 ∞
3 ∞ ∞ 1 0 6
4 6 ∞ ∞ ∞ 0
largest 7
3-(1) a,b
3-(2) b,c
3-(3) b,d
3-(4) b,d
3-(5) a,d
3-(6) after collaps
P
↗↑↑↖
K q r s p
↗ ↗↗↑↑↖↖
f i f k q r s
↗
i
3-(7) X=50 Y=11
3-(8)
H F
/ \ / \
B C B C
/ \ / \ OR / \ / \
D E F G D E I G
\ / \ /
I J H J
3-(9)
60
/ \
30 70
/ \ \
20 40 80
/ / \
10 35 50
3-10
(40, )
/ \
(20, ) (70, )
/ | / \
(10,)(30,)(60,)(80,)
3-11
*
/ \
4 80
/ \ / \
8 60 6 50
/ \ / \ / \ /
12 20 10 16 14 30 40
3-12 b,d
3-13 a,c
4
(1)
O o Ω ω Θ
A Y Y N N N
B N N Y Y N
C Y N Y N Y
(2) 8
(3)(A) Θ(n(logn)^2)
(B) Θ(n^(lg3))
(C) Θ(nlglgn)
(D) Θ(logn)
(E) Θ((logn)^2)
5-(1) 6
5-(2) merage sort
5-(3) 2
5-(4) 4
5-(5) 3
5-(6) │lgn!│ +1
└ ┘
5-(7) O(nlogn)
5-(8) No
5-(9) yes
5-(10) 23,17,14,6,13,10,1,5,7,12
| |
7 6
2 places change
6. 有请高手解之..
希望有写这份的可以一起讨论~
欢迎寄信或回(推)文
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.44.236.51
※ 编辑: taitin 来自: 114.44.236.51 (02/01 20:42)
1F：推 polomoss:後天要写~写完再跟你对~ 02/01 23:17
2F：推 hanbz:2-3的0到4为1 非无穷大 02/06 22:22
喔喔打错了，已修正感谢
※ 编辑: taitin 来自: 61.230.227.76 (02/07 00:04)
※ 编辑: taitin 来自: 61.230.220.229 (02/08 00:46)
3F：推 qwertz:1-3我算是 1+2+3+4+6+7+11 = 34 耶 02/08 17:29
4F：推 qwertz:5-2好像只有merge sort 02/08 17:44
我写错了，已修正
5F：→ qwertz:5-3 我写 2 ,merge sort 与 heap sort 02/08 17:46
6F：→ qwertz:5-4 我写 4 ,bubble insert quick selection 02/08 17:48
写反了囧，看着打都会打错QQ，已修正
7F：推 qwertz:5-9 的 algo 我想不出来 可以请教一下吗@@" 02/08 17:54
find(S,n/2);
find (S,k)
{
假设一个数列S有n个数，将S切个成数个集合，每个集合五个数字，因此共有(n/5)个集合
1.对每个集合排序 n/5* O(5log5)=O(n)
2.找到每个集合的中位数，即每个集合第3个数 O(1)
3.令S'=上述每个集合的中位数，m=find(S',(n/5)2) T(n/5)
4.则可利用M将S分成三个部份 S1(<m) S2(=m) S3(>m) O(n)
5.a. 若|S1|个数>=k，则第K数落在S1里面，find(S1,n/2) T(n/4)
b. 否则若|S1|+|S2|>=k，则第K数落在S2里面，return(m) O(1)
c. 否则find(s3,k-|s1|-|s2|); T(3n/4)
}
整体复杂度讨论
T(n)=T(n/5)+T(n/4)orT(3n/4)orO(1)+O(n)
=T(n/5)+T(3n/4)+O(n)
由於 1/5+3/4<1
因此
T(n)=O(n)
至於为什麽第四步是n/4
考虑下列情况
集合1
* * * * *
集合2
* * * * *
集合3
* * * * *
集合4 * * * * *
集合5 * * * * *
红色为上述演算法中的M
而由於每个序列都被排序，而红色点又是各集合中位数的中位数
因此可知道可以找到至少1/4的数字小於m
因此可知道|S1|最多只有n/4
而|S3|最多只有3n/4(若s2不存在)
8F：推 hanbz:1-3 我也是算34= = 02/08 17:54
1-3我算错了，已修正感谢楼上两位
※ 编辑: taitin 来自: 61.230.226.58 (02/08 21:08)
※ 编辑: taitin 来自: 140.113.7.249 (02/09 13:01)
9F：推 stevenwin:请问1-1答案是 -1 -1 0 1 2 0 吗? 02/09 23:14
恩，是0我打错了ˊˋ
※ 编辑: taitin 来自: 61.230.226.58 (02/09 23:20)
10F：推 stevenwin:想问 4 (1) A 的 big-O 和 B 的 Omega为何都是yes? 02/09 23:27
11F：→ stevenwin:4 (2) 请问是哪8个是polynomial bounded? 02/09 23:29
12F：推 qwertz:4 (2)我选的是从头到尾数来 第 2 3 4 5 9 10 14 15这八个 02/09 23:39
跟我一样
13F：→ qwertz:4 (1) A是P(n)的绝对上界(小big-o) 所以也是P(n)的big-O 02/09 23:40
14F：→ qwertz:4 (2) B则是P(n)的绝对下界(小omega)所以也是P(n)的大Omega 02/09 23:42
15F：→ qwertz: (1) 上一行打错 02/09 23:42
16F：推 stevenwin:常数算是polynomial bounded? 想说常数可以想成n^0 02/09 23:48
17F：→ stevenwin:我终於了解了，感谢!! 02/09 23:50
18F：推 polomoss:2(1)应该就是建立max-heap 02/10 01:16
他程式有没有错阿？好像跑不出来。
19F：推 polomoss:3(1)请问c错在哪~? 02/10 01:19
20F：→ polomoss:3(3)可以解释一下a.c错在哪吗? 02/10 01:20
21F：→ polomoss:4(2) 我算10个，4(3)(C)nlglgn 02/10 01:21
22F：推 qwertz:3(1)的c 应该是theta(nlogn)而不是O(nlogn) 02/10 15:58
23F：→ qwertz:而3(3) a错在recursion 应是 T(n) = 2T(2/n) + (n-1) 02/10 16:00
应该还是T(n) = 2T(n/2) + cn，但是不见得balance造成best result
24F：→ qwertz:而3(3)的 c有点像是玩文字游戏 我是想quick sort 虽然有 02/10 16:01
25F：→ qwertz:最高的performance 但是并不能说他是代表comparison sort中 02/10 16:02
26F：→ qwertz:复杂度最低的 02/10 16:02
跟楼上想法大致相同，我认为不能说某个演算法是最好的，
这个问题最佳解的复杂度就是这样，因为也许有更好的演算法只是没被发现而已。
27F：推 qwertz:另外4(3) 我也是算 nlglgn polomoss请问你4(2)选哪几个@@? 02/10 16:07
4(3)我算错，已修正，感谢二位
※ 编辑: taitin 来自: 140.113.7.249 (02/10 18:28)
※ 编辑: taitin 来自: 140.113.7.249 (02/10 18:33)
※ 编辑: taitin 来自: 61.230.219.56 (02/15 19:26)
28F：推 stevenwin:2(3) 我最大写13耶 02/23 01:03
29F：→ taitin:题目是 A1的意思是可以通过vetex number 1到达其他点 02/23 01:08
※ 编辑: taitin 来自: 220.136.209.215 (03/08 18:33)
※ 编辑: taitin 来自: 220.136.209.215 (03/08 18:34)
30F：推 hswayne:(3) all-pairs那一题答案13吧 03/08 19:21
31F：→ KarmaPolice:我也写13 03/09 18:01
32F：推 zensword:13 +1 02/14 19:33