作者mqazz1 (无法显示)
看板Math
标题[演算法] 时间复杂度
时间Sun Feb 6 23:28:32 2011
ture or false
1. O(n^2) + O(n^3) = O(n^4)
2. O(n^2) * O(n^3) = O(n^5)
3. O(n) ^ O(lgn) = O(2^n)
请问这几题要怎麽判断呢?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.24.214
1F：推 jameschou :true true true .........吧! 一眼看过去直观是这样 02/06 23:32
2F：→ charliejack :我是试着把数字带进去呀~ O() 是Upper bound 02/06 23:34
3F：→ charliejack :所以 n^2 + n^3 = O(n^4) 02/06 23:36
4F：→ charliejack :n^2*n^3 = n^5 = O(n^5) 这是符合的 因为你已经带入 02/06 23:36
5F：→ charliejack :bigO里面最大的数 不会有例外产生 So It's for all 02/06 23:37
6F：→ charliejack :第三题 全部把左边BigO 除掉 做Log 会变成 02/06 23:38
7F：→ charliejack :lgn^2 和 2^n 取log 变成 nlog2 => nlog2 > lgn^2 02/06 23:39
8F：→ charliejack :所以一定符合第三题的all case 02/06 23:40
9F：→ charliejack :第一次解题 不对的地方 请版众 和 大大们指教@@" 02/06 23:40
10F：→ charliejack :我想应该有更合理的解释~ 02/06 23:41
11F：推 hcsoso :想要请问你们有需要用严谨的 big-O 定义证明吗? 02/07 00:18
12F：→ hcsoso :直观上都是对的没有错. 02/07 00:19