作者wang19980531 (柯黑战神 第一英粉)
看板Grad-ProbAsk
标题[理工] 资结 时间复杂度 2题
时间Sat Jul 27 22:46:30 2019
1. 该如何说明
(loglogn)! 为一个polynomially bounded function?
2. 原题目如下，不晓得C为何错误
We abuse the “ + “ operator with asymptotic notations. For example , we may sa
y that the total time for an algorithm is O(n) + Θ(n). Which of the following s
tatement are true.
A. O(nlogn)+ Θ(n^2)= Θ(n^2)
B. O(n^2)+ Θ(n^2)= Θ(n^2)
C. O(nlogn)+ Θ(nlogn) = O(nlogn)
D. O(n^2)+O(nlogn)= Θ(n^2)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.247.70.195 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1564238792.A.D2C.html
1F：推 james80351: 第一题就取log 最後要推到O(log n)呀 07/28 00:10
3F：→ JKLee: =是指集合的belong还是equual 07/28 00:12
4F：→ JKLee: ? 07/28 00:12
5F：→ mistel: 第二题我不知道 因为这是定理，但我觉得也成立就是了... 07/28 00:13
6F：推 mistel: 楼上，是集合的belong 07/28 00:16
7F：→ JKLee: 若是equal,则c错 07/28 00:16
8F：→ JKLee: 若是belong,则c对 07/28 00:17
9F：→ wang19980531: 谢谢大家 07/28 14:13
10F：推 ekids1234: 为何 equal 错呀 07/28 17:44
11F：→ wang19980531: 对耶 刚看了一下 theta(nlogn)不就表示平均是nlogn 07/28 20:48
12F：→ wang19980531: 那麽说复杂度最少就是O(nlogn)吧？ 07/28 20:48
14F：→ jls16457: 顺带一提，theta跟跟平均应该是不一样的哦 07/28 22:00
15F：→ wang19980531: 意思是 theta(n) <=> O(n)and omega (n) 07/29 10:41
16F：→ wang19980531: 所以C已经确认范围是夹集 应该要写theta(nlogn) ? 07/29 10:41