推 anoymouse: 就是結論沒錯 但是最好情況跟abcdefgoogle的大O是錯的 12/15 14:06
→ anoymouse: 這樣 對嗎？ 12/15 14:06
我只敢說我是這麼認為的XD
※ 編輯: ddavid (114.32.17.60 臺灣), 12/15/2020 15:10:39
推 anoymouse: 瞭解 謝謝d大的詳解～ 12/15 15:26
※ 引述《anoymouse (沒有暱稱)》之銘言：
: https://imgur.com/O5P83PO
: https://imgur.com/Pz3PwRP
先澄清變數，n是主串長度，m是要找的子串長度，問題應該是我們要從主串裡面
找到子串吧。
: 1.請教為什麼"googlegood"字串搜尋"google"是 O(1)?
: 就算第一個位置就是了，迴圈還是要跑google這個字串長度的次數才有找到吧?
如你所說，應該是m次 -> O(m)。
: 2. "abcdefgoogle" 為什麼又是O(m + n)? 迴圈abcdef都走else，碰到'g'開始走if
: 不是else部分( m - n) 次 + if部分 n 次 = m次 ?
同樣如你所說，應該是n次 -> O(n)。
: 機率原則為什麼是(m+n)/2?
等機率原則是這麼思考的：
所謂的最佳情況，就是沒走到岔路的所有情況。也就是說同樣n長度的主串與同
樣長度m的子串而言：
[長度0] [長度m] [長度n-m]
google abcdef -> O(m)
[長度1] [長度m] [長度n-(m+1)]
a google bcdef
.
.
[長度(n-m)] [長度m] [長度0]
abcdef google -> O(n)
每一個情況的發生機率是相等的。所以把最佳情況跟最差情況相加除以二（平均
）會等同於所有情況的平均（梯形取中間寬度的意思）。
所以其實他結論算是沒錯，(n + m)/2 -> O(n+m)。但是他是用(1+(n+m))/2湊出
來剛好賽中O(n+m)的XD
--
「傳說的最後，魔王總是被勇者封印。但勇者會逝去、封印會衰弱，魔王卻永遠
不滅。傳說呢？傳說持續著。只是，變質了。所以對於傳說而言，只有反覆無常的自
己是主角，而魔王只是配角。勇者？勇者不過是消耗品罷了，封印則什麼也不是。妳
好不容易有機會當上配角，怎麼走回頭路想成為消耗品？妳早晚會什麼也不是的。」
－－星．幻．夢的傳說
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.17.60 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1608009661.A.0C6.html