作者查詢 / suhorng

總覽項目：發文 | 留言 | 暱稱

作者 suhorng 在 PTT [ Prob_Solve ] 看板的留言(推文), 共337則

限定看板：Prob_Solve

看板排序：

全部C_Chat5350Math2497LightNovel1315C_and_CPP1218NTU423Prob_Solve337trans_math282Programming222CFantasy183NTUcourse143PLT110ck-talk103studyabroad76TOEFL_iBT75b00902HW71Grad-ProbAsk59SENIORHIGH57SMSlife48ASM44b00902xxx37Shana37GRE28NTU-Exam23Soft_Job22DoubleMajor21CSSE19Army-Sir15logic15juniorhigh14PangSir14CSCouncil13C_BOO11CKEISC10b98902xxx9Nangang8PHP8Python8b04902xxx7Gossiping7graduate6KanColle6Kyoto_Ani6b98902HW4b99902HW4b99902xxx4CS_TEACHER4CSIE_WSLAB4joke4KS98-3024LaTeX4love-vegetal4Militarylife4NTUHistory024Sub_CS4SYSOP4AC_In3b01902HW3b01902xxx3BBSmovie3CompilerDev3IdolMaster3NTUMG3Shokugeki3Suckcomic3Translate-CS3AfterPhD2Agr-Football2asciiart2b02902xxx2ck-inforOLD2ck60th1282CodeJob2H-GAME2Isayama2Libra2NTUMEB012NTUSA2specialman2StupidClown2SummerCourse2Ajax1ArakawaCow1ask1Aviation1B00305XXX1B00310XXX1b974060XX1b97902HW1Beauty1bi-sexual1Buddha1Buddhism1Bus1Capricornus1civil971ck58th3241ck61st1031ck61st3221ck61st3261ckbc1ComGame-Plan1CompBook1CSIE_Service1Daan1dog1DragonNest1Electronics1Evangelion1Fallinlove1FCU-EES1FinalFantasy1Gamesale1GetMarry1historia1home-sale1HSNU_11431IMO_Taiwan1Jeremy_Lin1JYPnation1KMSH_MS981KNU1Koei1KS97-3021KS97-3101LamiGirls1Linux1love1LoveLive_Sip1marriage1MCU_Talk1MH1Military1mobilesales1NCCU1NCHU-FT-1011NCHU_CsHsnu1NDHU-LF981NIHONGO1Nogizaka461NPTU1NTU_Service1ntuACCT031ntuACCT041NTUBA041NTUDMCC1NTUEE1151NTUfin061NTUMath1001NTUMEB001NTUmed001NTUSFA1NTUST_Talk1NTUT_EE496B1Pangya1part-time1PC_Shopping1PCSH96_3061piano1Pisces1pity1PuzzleDragon1Queer_drama1Railway1RakutenGirls1sex1sky1SRW1StarTrek1Stock1Suckgame1SuperBike1TakahashiRie1TOEIC1TokyoGhoul1Transfer1transgender1TTU-EE991TTU-I90B1TW-GHONOR1TWopera1uniform1Unlight1USC1VISA1Visual_Basic1Wen-Shan1Windows1WOW1WuYiFan1Yabuki1YZU_EE95B1Zhongzheng1<< 收起看板(192)

首頁

尾頁

[問題] 何謂 bottleneck spanning tree ?

[ Prob_Solve ]16 留言, 推噓總分: +3

作者: woody3724 - 發表於 2011/12/19 19:48(12年前)

1^F推suhorng:無向、帶權圖G可能有很多個生成樹每棵生成樹都會有權重最12/19 19:59

2^F→suhorng:大的邊 (可能一條, 可能很多條)12/19 19:59

3^F→suhorng:在這很多棵生成樹中 {權重最大的邊}最小的那棵稱為MBST12/19 19:59

4^F→suhorng:對某棵生成樹而言, 權重最大的那條邊叫做bottleneck edge12/19 20:00

5^F→suhorng:維基之所以說MBST是"沒有bottleneck edge比它更小的生成樹12/19 20:01

6^F→suhorng:的spanning tree稱為MBST",是因為可能有很多棵MBST12/19 20:01

12^F推suhorng:**完全**沒有說權和加起來要最小只要求最大邊最小12/20 09:18

13^F→suhorng:對於某一棵生成樹T 我們稱T中權最大的邊bottleneck edge12/20 09:21

14^F→suhorng:若對某棵T而言不存在T' 使得T'的bottleneck edge的權 <12/20 09:21

15^F→suhorng:T的bottleneck edge的權那就說T是一棵MBST12/20 09:22

16^F→suhorng:別把他跟MST弄混了~ 雖然一樣可以用修改的Kruskal's求MBST12/20 09:22

[問題] unbounded search

[ Prob_Solve ]6 留言, 推噓總分: +2

作者: mqazz1 - 發表於 2011/12/10 20:39(12年前)

2^F→suhorng:可以請問題目原文在哪 ~?12/11 11:09

[問題] 有向圖的自達點

[ Prob_Solve ]5 留言, 推噓總分: +2

作者: sbshank - 發表於 2011/11/16 22:03(12年前)

1^F推suhorng:找出SCC. 所有在點數>1的SCC中的點必定可以,反之不行11/16 23:08

2^F→suhorng:其時間複雜度為O(V+E)11/16 23:08

4^F→suhorng:樓上有道理....self-cycle要Special Case判掉orz11/17 08:16

[問題] 單紙帶圖靈機與 o(n log n)

[ Prob_Solve ]9 留言, 推噓總分: +3

作者: suhorng - 發表於 2011/11/08 23:22(12年前)

5^F→suhorng:感謝一樓:) 用至這個當關鍵字搜尋到神奇的東西:11/09 21:36

6^F→suhorng: http://cc-li.blog.ntu.edu.tw/files/2011/01/11/09 21:36

7^F→suhorng: 2010final_sol.pdf11/09 21:36

8^F→suhorng:裡面 Problem 5 是這題並有解答...11/09 21:37

Re: [問題] 計算時間複雜度

[ Prob_Solve ]12 留言, 推噓總分: +3

作者: lf963 - 發表於 2011/11/08 22:29(12年前)

4^F→suhorng:可以請問樓上第一行是怎麼來的..?11/08 22:58

5^F→suhorng:另外, n!≦n^n 但 lg(n!)=Θ(nlgn), lg(n^n)=Θ(nlgn)...11/08 23:03

11^F→suhorng:@lf963: 我的意思是說取lg相等不代表他們相等11/09 10:26

12^F→suhorng:所以取lg無法得到結論11/09 10:27

[問題] multiselection

[ Prob_Solve ]2 留言, 推噓總分: 0

作者: mqazz1 - 發表於 2011/11/07 20:22(12年前)

1^F→suhorng:divide and conquer on r, with O(n) selection algorithm11/07 20:26

[問題] 0/1背包問題的時間複雜度

[ Prob_Solve ]7 留言, 推噓總分: +2

作者: i78524 - 發表於 2011/10/24 19:37(12年前)

2^F→suhorng:我自己是覺得...因為W是輸入的"數值"範圍, 不是"數量"範圍10/24 19:50

3^F→suhorng:但以上只是我自己的想法...我沒修過課沒唸過...10/24 19:50

[問題] 計算時間複雜度

[ Prob_Solve ]3 留言, 推噓總分: +1

作者: p7pp7 - 發表於 2011/10/05 21:26(12年前)

1^F推suhorng:1沒錯 2是Θ(log n), 這個可以從∫1/x dx來看 (上/下界)10/05 21:31

2^F→suhorng:或是單純每次取 2, 4, 8, 16, 32, ... 項, 看上下界10/05 21:31

[問題] 程式執行複雜度

[ Prob_Solve ]5 留言, 推噓總分: +1

作者: mqazz1 - 發表於 2011/10/01 19:52(12年前)

3^F→suhorng:猜: O(nlogn) O((log n)^2) O(n^2), and k恆等於0 ?10/01 20:43

4^F→suhorng:第四個我是把for當成if來猜...10/01 20:43

[問題] 時間複雜度疑問

[ Prob_Solve ]13 留言, 推噓總分: +4

作者: DJWS - 發表於 2011/09/28 15:27(12年前)

7^F→suhorng:可是AKS我記得是lg ? 那就不是與長度成指數次方關係了？09/29 14:32

首頁

尾頁