作者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