作者ddavid (谎言接线生)
看板C_and_CPP
标题Re: [问题] 范例的时间复杂度
时间Tue Dec 15 13:20:57 2020
※ 引述《anoymouse (没有昵称)》之铭言：
: https://imgur.com/O5P83PO
: https://imgur.com/Pz3PwRP
先澄清变数，n是主串长度，m是要找的子串长度，问题应该是我们要从主串里面
找到子串吧。
: 1.请教为什麽"googlegood"字串搜寻"google"是 O(1)?
: 就算第一个位置就是了，回圈还是要跑google这个字串长度的次数才有找到吧?
如你所说，应该是m次 -> O(m)。
: 2. "abcdefgoogle" 为什麽又是O(m + n)? 回圈abcdef都走else，碰到'g'开始走if
: 不是else部分( m - n) 次 + if部分 n 次 = m次 ?
同样如你所说，应该是n次 -> O(n)。
: 机率原则为什麽是(m+n)/2?
等机率原则是这麽思考的：
所谓的最佳情况，就是没走到岔路的所有情况。也就是说同样n长度的主串与同
样长度m的子串而言：
[长度0] [长度m] [长度n-m]
google abcdef -> O(m)
[长度1] [长度m] [长度n-(m+1)]
a google bcdef
.
.
[长度(n-m)] [长度m] [长度0]
abcdef google -> O(n)
每一个情况的发生机率是相等的。所以把最佳情况跟最差情况相加除以二（平均
）会等同於所有情况的平均（梯形取中间宽度的意思）。
所以其实他结论算是没错，(n + m)/2 -> O(n+m)。但是他是用(1+(n+m))/2凑出
来刚好赛中O(n+m)的XD
--
「传说的最後，魔王总是被勇者封印。但勇者会逝去、封印会衰弱，魔王却永远
不灭。传说呢？传说持续着。只是，变质了。所以对於传说而言，只有反覆无常的自
己是主角，而魔王只是配角。勇者？勇者不过是消耗品罢了，封印则什麽也不是。你
好不容易有机会当上配角，怎麽走回头路想成为消耗品？你早晚会什麽也不是的。」
－－星．幻．梦的传说
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.32.17.60 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1608009661.A.0C6.html
1F：推 anoymouse: 就是结论没错 但是最好情况跟abcdefgoogle的大O是错的 12/15 14:06
2F：→ anoymouse: 这样 对吗？ 12/15 14:06
我只敢说我是这麽认为的XD
※ 编辑: ddavid (114.32.17.60 台湾), 12/15/2020 15:10:39
3F：推 anoymouse: 了解 谢谢d大的详解～ 12/15 15:26