作者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/cn.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