书籍:大话资料结构
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?
谢谢

他不是说是最好的情况了吗噢我懂你意思了 你觉得是O(n)吗

我觉得是O(n)

n是比较长的主串，m是要找的子串，所以1应该是o(m)，2是o(n)吧

哦哦 我写反了 对n是主串比较长但我查作者网站上的勘误表 没有提到这边有错误

1. 我猜作者可能把m视为常数？所以O(m) = O(1)，代表常数的复杂度2. m+n应该是最糟的状况，在else子句中，会有倒退的现象，所以平均必大于m。而会除2大概是取最佳+最糟的平均。**平均比大于n**所以“最糟”必大于“n”，因为会倒退数次后来想想除2，应该是因为最糟是把正解摆在最后面，甚至没有答案，中途还倒退数次。而平均应假设正解在字串中央，所以/2

m视为常数的话下面又用O(n+m)就是自我矛盾了/2就是因为平均分布的情况下取(最好+最差)/2等于整体平均我回的那一篇有解释另外ttsung2你有个小误解，这一段其实在计算的都是最佳情况，最糟情况在下一段这边所谓的“最佳情况”是指“找到正解之前没有经历任何找错倒退”，以正解google为例就是之前完全没出现过g所以不会进到岔路倒退这样所以虽然有点像绕口令，但他这段先把最佳情况的最佳情况跟最差的最佳情况（XD）都分析出来，然后用等机率原则来得到最佳情况的平均复杂度