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

看板C_and_CPP (C/C++)作者ddavid (謊言接線生)時間4年前 (2020/12/15 13:21)推噓2(2推 0噓 1→)

留言3則, 1人參與討論串2/2 (看更多)

※ 引述《anoymouse (沒有暱稱)》之銘言： : https://imgur.com/O5P83PO

先澄清變數，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