[問題] 範例的時間複雜度

看板C_and_CPP作者 (沒有暱稱)時間3年前 (2020/12/14 23:03), 3年前編輯推噓2(2推 0噓 25→)
留言27則, 4人參與, 3年前最新討論串1/2 (看更多)
書籍:大話資料結構 https://imgur.com/O5P83PO
https://imgur.com/Pz3PwRP
1.請教為什麼"googlegood"字串搜尋"google"是 O(1)? 就算第一個位置就是了，迴圈還是要跑google這個字串長度的次數才有找到吧? 2. "abcdefgoogle" 為什麼又是O(m + n)? 迴圈abcdef都走else，碰到'g'開始走if 不是else部分( m - n) 次 + if部分 n 次 = m次 ? 機率原則為什麼是(m+n)/2? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.136.56.200 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1607958204.A.63A.html ※ 編輯: anoymouse (220.136.56.200 臺灣), 12/14/2020 23:04:23
→
12/14 23:11, 3年前 , 1F
他不是說是最好的情況了嗎
12/14 23:11, 1F
→
12/14 23:12, 3年前 , 2F
噢我懂你意思了 你覺得是O(n)嗎
12/14 23:12, 2F
→
12/14 23:15, 3年前 , 3F
我覺得是O(n)
12/14 23:15, 3F
推
12/15 10:08, 3年前 , 4F
n是比較長的主串，m是要找的子串，所以1應該是o(m)，2是
12/15 10:08, 4F
→
12/15 10:08, 3年前 , 5F
o(n)吧
12/15 10:08, 5F
→
12/15 11:16, 3年前 , 6F
哦哦 我寫反了 對n是主串比較長
12/15 11:16, 6F
→
12/15 11:17, 3年前 , 7F
但我查作者網站上的勘誤表 沒有提到這邊有錯誤
12/15 11:17, 7F
→
12/16 00:27, 3年前 , 8F
1. 我猜作者可能把m視為常數？所以O(m) = O(1)，代表常
12/16 00:27, 8F
→
12/16 00:27, 3年前 , 9F
數的複雜度
12/16 00:27, 9F
→
12/16 00:31, 3年前 , 10F
2. m+n應該是最糟的狀況，在else子句中，會有倒退的現象
12/16 00:31, 10F
→
12/16 00:31, 3年前 , 11F
，所以平均必大於m。而會除2大概是取最佳+最糟的平均。
12/16 00:31, 11F
→
12/16 00:32, 3年前 , 12F
**平均比大於n
12/16 00:32, 12F
→
12/16 00:45, 3年前 , 13F
**所以「最糟」必大於「n」，因為會倒退數次
12/16 00:45, 13F
→
12/16 00:48, 3年前 , 14F
後來想想除2，應該是因為最糟是把正解擺在最後面，甚至
12/16 00:48, 14F
→
12/16 00:48, 3年前 , 15F
沒有答案，中途還倒退數次。
12/16 00:48, 15F
→
12/16 00:48, 3年前 , 16F
而平均應假設正解在字串中央，所以/2
12/16 00:48, 16F
推
12/16 17:45, 3年前 , 17F
m視為常數的話下面又用O(n+m)就是自我矛盾了
12/16 17:45, 17F
→
12/16 17:46, 3年前 , 18F
/2就是因為平均分佈的情況下取(最好+最差)/2等於整體平均
12/16 17:46, 18F
→
12/16 17:52, 3年前 , 19F
我回的那一篇有解釋
12/16 17:52, 19F
→
12/16 17:53, 3年前 , 20F
另外ttsung2你有個小誤解，這一段其實在計算的都是最佳情
12/16 17:53, 20F
→
12/16 17:53, 3年前 , 21F
況，最糟情況在下一段
12/16 17:53, 21F
→
12/16 17:54, 3年前 , 22F
這邊所謂的「最佳情況」是指「找到正解之前沒有經歷任何找
12/16 17:54, 22F
→
12/16 17:55, 3年前 , 23F
錯倒退」，以正解google為例就是之前完全沒出現過g所以不
12/16 17:55, 23F
→
12/16 17:55, 3年前 , 24F
會進到岔路倒退這樣
12/16 17:55, 24F
→
12/16 17:56, 3年前 , 25F
所以雖然有點像繞口令，但他這段先把最佳情況的最佳情況跟
12/16 17:56, 25F
→
12/16 17:57, 3年前 , 26F
最差的最佳情況（XD）都分析出來，然後用等機率原則來得到
12/16 17:57, 26F
→
12/16 17:57, 3年前 , 27F
最佳情況的平均複雜度
12/16 17:57, 27F
‣ 更多 anoymouse 的文章
文章代碼(AID): #1VrtwyOw (C_and_CPP)
‣ 更多 anoymouse 的文章
文章代碼(AID): #1VrtwyOw (C_and_CPP)