[理工] [資結]-交大98-資訊聯招-DS&algo核對

看板Grad-ProbAsk作者 (小南)時間16年前 (2010/02/01 19:42), 編輯推噓17(17推 0噓 15→)
留言32則, 8人參與, 最新討論串1/9 (看更多)
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)
推
02/01 23:17, , 1F
後天要寫~寫完再跟你對~
02/01 23:17, 1F
推
02/06 22:22, , 2F
2-3的0到4為1 非無窮大
02/06 22:22, 2F
喔喔打錯了，已修正感謝 ※ 編輯: taitin 來自: 61.230.227.76 (02/07 00:04) ※ 編輯: taitin 來自: 61.230.220.229 (02/08 00:46)
推
02/08 17:29, , 3F
1-3我算是 1+2+3+4+6+7+11 = 34 耶
02/08 17:29, 3F
推
02/08 17:44, , 4F
5-2好像只有merge sort
02/08 17:44, 4F
我寫錯了，已修正
→
02/08 17:46, , 5F
5-3 我寫 2 ,merge sort 與 heap sort
02/08 17:46, 5F
→
02/08 17:48, , 6F
5-4 我寫 4 ,bubble insert quick selection
02/08 17:48, 6F
寫反了囧，看著打都會打錯QQ，已修正
推
02/08 17:54, , 7F
5-9 的 algo 我想不出來 可以請教一下嗎@@"
02/08 17:54, 7F
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不存在)
推
02/08 17:54, , 8F
1-3 我也是算34= =
02/08 17:54, 8F
1-3我算錯了，已修正感謝樓上兩位 ※ 編輯: taitin 來自: 61.230.226.58 (02/08 21:08) ※ 編輯: taitin 來自: 140.113.7.249 (02/09 13:01)
推
02/09 23:14, , 9F
請問1-1答案是 -1 -1 0 1 2 0 嗎?
02/09 23:14, 9F
恩，是0我打錯了ˊˋ ※ 編輯: taitin 來自: 61.230.226.58 (02/09 23:20)
推
02/09 23:27, , 10F
想問 4 (1) A 的 big-O 和 B 的 Omega為何都是yes?
02/09 23:27, 10F
→
02/09 23:29, , 11F
4 (2) 請問是哪8個是polynomial bounded?
02/09 23:29, 11F
推
02/09 23:39, , 12F
4 (2)我選的是從頭到尾數來 第 2 3 4 5 9 10 14 15這八個
02/09 23:39, 12F
跟我一樣
→
02/09 23:40, , 13F
4 (1) A是P(n)的絕對上界(小big-o) 所以也是P(n)的big-O
02/09 23:40, 13F
→
02/09 23:42, , 14F
4 (2) B則是P(n)的絕對下界(小omega)所以也是P(n)的大Omega
02/09 23:42, 14F
→
02/09 23:42, , 15F
(1) 上一行打錯
02/09 23:42, 15F
推
02/09 23:48, , 16F
常數算是polynomial bounded? 想說常數可以想成n^0
02/09 23:48, 16F
→
02/09 23:50, , 17F
我終於瞭解了，感謝!!
02/09 23:50, 17F
推
02/10 01:16, , 18F
2(1)應該就是建立max-heap
02/10 01:16, 18F
他程式有沒有錯阿？好像跑不出來。
推
02/10 01:19, , 19F
3(1)請問c錯在哪~?
02/10 01:19, 19F
→
02/10 01:20, , 20F
3(3)可以解釋一下a.c錯在哪嗎?
02/10 01:20, 20F
→
02/10 01:21, , 21F
4(2) 我算10個，4(3)(C)nlglgn
02/10 01:21, 21F
推
02/10 15:58, , 22F
3(1)的c 應該是theta(nlogn)而不是O(nlogn)
02/10 15:58, 22F
→
02/10 16:00, , 23F
而3(3) a錯在recursion 應是 T(n) = 2T(2/n) + (n-1)
02/10 16:00, 23F
應該還是T(n) = 2T(n/2) + cn，但是不見得balance造成best result
→
02/10 16:01, , 24F
而3(3)的 c有點像是玩文字遊戲 我是想quick sort 雖然有
02/10 16:01, 24F
→
02/10 16:02, , 25F
最高的performance 但是並不能說他是代表comparison sort中
02/10 16:02, 25F
→
02/10 16:02, , 26F
複雜度最低的
02/10 16:02, 26F
跟樓上想法大致相同，我認為不能說某個演算法是最好的， 這個問題最佳解的複雜度就是這樣，因為也許有更好的演算法只是沒被發現而已。
推
02/10 16:07, , 27F
另外4(3) 我也是算 nlglgn polomoss請問你4(2)選哪幾個@@?
02/10 16:07, 27F
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)
推
02/23 01:03, , 28F
2(3) 我最大寫13耶
02/23 01:03, 28F
→
02/23 01:08, , 29F
題目是 A1的意思是可以通過vetex number 1到達其他點
02/23 01:08, 29F
※ 編輯: taitin 來自: 220.136.209.215 (03/08 18:33) ※ 編輯: taitin 來自: 220.136.209.215 (03/08 18:34)
推
03/08 19:21, , 30F
(3) all-pairs那一題答案13吧
03/08 19:21, 30F
→
03/09 18:01, , 31F
我也寫13
03/09 18:01, 31F
推
02/14 19:33, , 32F
13 +1
02/14 19:33, 32F
‣ 更多 taitin 的文章
文章代碼(AID): #1BPhuC4b (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 9 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共9篇)
‣ 更多 taitin 的文章
文章代碼(AID): #1BPhuC4b (Grad-ProbAsk)