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

[anoymouse (沒有暱稱)]

書籍:大話資料結構

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