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

作者: anoymouse (沒有暱稱)   2020-12-14 23:03:22
書籍:大話資料結構
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?
謝謝
作者: mmmmei (mmm煤)   2020-12-14 23:11:00
他不是說是最好的情況了嗎噢我懂你意思了 你覺得是O(n)嗎
作者: anoymouse (沒有暱稱)   2020-12-14 23:15:00
我覺得是O(n)
作者: ddavid (謊言接線生)   2020-12-15 10:08:00
n是比較長的主串,m是要找的子串,所以1應該是o(m),2是o(n)吧
作者: anoymouse (沒有暱稱)   2020-12-15 11:16:00
哦哦 我寫反了 對n是主串比較長但我查作者網站上的勘誤表 沒有提到這邊有錯誤
作者: ttsung2 (宗宗)   2020-12-16 00:27:00
1. 我猜作者可能把m視為常數?所以O(m) = O(1),代表常數的複雜度2. m+n應該是最糟的狀況,在else子句中,會有倒退的現象,所以平均必大於m。而會除2大概是取最佳+最糟的平均。**平均比大於n**所以「最糟」必大於「n」,因為會倒退數次後來想想除2,應該是因為最糟是把正解擺在最後面,甚至沒有答案,中途還倒退數次。而平均應假設正解在字串中央,所以/2
作者: ddavid (謊言接線生)   2020-12-16 17:45:00
m視為常數的話下面又用O(n+m)就是自我矛盾了/2就是因為平均分佈的情況下取(最好+最差)/2等於整體平均我回的那一篇有解釋另外ttsung2你有個小誤解,這一段其實在計算的都是最佳情況,最糟情況在下一段這邊所謂的「最佳情況」是指「找到正解之前沒有經歷任何找錯倒退」,以正解google為例就是之前完全沒出現過g所以不會進到岔路倒退這樣所以雖然有點像繞口令,但他這段先把最佳情況的最佳情況跟最差的最佳情況(XD)都分析出來,然後用等機率原則來得到最佳情況的平均複雜度

Links booklink

Contact Us: admin [ a t ] ucptt.com