作者anoymouse (沒有暱稱)
看板C_and_CPP
標題[問題] 範例的時間複雜度
時間Mon Dec 14 23:03:22 2020
書籍:大話資料結構
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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1607958204.A.63A.html
※ 編輯: anoymouse (220.136.56.200 臺灣), 12/14/2020 23:04:23
1F：→ mmmmei: 他不是說是最好的情況了嗎 12/14 23:11
2F：→ mmmmei: 噢我懂你意思了 你覺得是O(n)嗎 12/14 23:12
3F：→ anoymouse: 我覺得是O(n) 12/14 23:15
4F：推 ddavid: n是比較長的主串，m是要找的子串，所以1應該是o(m)，2是 12/15 10:08
5F：→ ddavid: o(n)吧 12/15 10:08
6F：→ anoymouse: 哦哦 我寫反了 對n是主串比較長 12/15 11:16
7F：→ anoymouse: 但我查作者網站上的勘誤表 沒有提到這邊有錯誤 12/15 11:17
8F：→ ttsung2: 1. 我猜作者可能把m視為常數？所以O(m) = O(1)，代表常 12/16 00:27
9F：→ ttsung2: 數的複雜度 12/16 00:27
10F：→ ttsung2: 2. m+n應該是最糟的狀況，在else子句中，會有倒退的現象 12/16 00:31
11F：→ ttsung2: ，所以平均必大於m。而會除2大概是取最佳+最糟的平均。 12/16 00:31
12F：→ ttsung2: **平均比大於n 12/16 00:32
13F：→ ttsung2: **所以「最糟」必大於「n」，因為會倒退數次 12/16 00:45
14F：→ ttsung2: 後來想想除2，應該是因為最糟是把正解擺在最後面，甚至 12/16 00:48
15F：→ ttsung2: 沒有答案，中途還倒退數次。 12/16 00:48
16F：→ ttsung2: 而平均應假設正解在字串中央，所以/2 12/16 00:48
17F：推 ddavid: m視為常數的話下面又用O(n+m)就是自我矛盾了 12/16 17:45
18F：→ ddavid: /2就是因為平均分佈的情況下取(最好+最差)/2等於整體平均 12/16 17:46
19F：→ ddavid: 我回的那一篇有解釋 12/16 17:52
20F：→ ddavid: 另外ttsung2你有個小誤解，這一段其實在計算的都是最佳情 12/16 17:53
21F：→ ddavid: 況，最糟情況在下一段 12/16 17:53
22F：→ ddavid: 這邊所謂的「最佳情況」是指「找到正解之前沒有經歷任何找 12/16 17:54
23F：→ ddavid: 錯倒退」，以正解google為例就是之前完全沒出現過g所以不 12/16 17:55
24F：→ ddavid: 會進到岔路倒退這樣 12/16 17:55
25F：→ ddavid: 所以雖然有點像繞口令，但他這段先把最佳情況的最佳情況跟 12/16 17:56
26F：→ ddavid: 最差的最佳情況（XD）都分析出來，然後用等機率原則來得到 12/16 17:57
27F：→ ddavid: 最佳情況的平均複雜度 12/16 17:57