※ 引述《taitin (小南)》之铭言： : 这是我自己写的答案，希望跟大家讨论一下 : 附上题目 : http://www.lib.ntu.edu.tw/exam/graduate/98/98404.pdf : 1. (1) G G(跟你同) : (2) H F : (3) L D : (4) E E(跟你同) : (5) H 原本想I ，不过我验算後改H compute(n,1): 第一小题 X为 【5】 Y为 【n/4取下限】 Z为 【n*n^(1/2)】 第一个for x←1～5 要做5次递回compute(n/4取下限, x*t) 每个递回的下面还要再做5次递回... ... .. 至於递回的次数有多深 端看 【Y不断的(n/4取下限)，何时到达<=1】 那就是5^(log n) = n^(log 5) 4 4 第二个for z←1 ~ n*n^(1/2) 每次处理 1单位时间 theta(1) 就是theta(n*n^(1/2)) 答案: theta ( n^(log 5) ) + theta( n*n^(1/2) ) 4 (右边的成长比较快) => O(n*n^(1/2)) 选G ------------------ 第二小题 X为4 Y为 n/2取下限 Z为 n^2 第一个for x←1～4 4次递回... 递回的次数深度....取决【Y不断的(n/2取下限)，何时到达<=1】 => 4^(log n) =>n^(log 4) => n^2 2 2 第二个for z←1 ~ n^2 => theta(n^2) 答案: theta(n^2) + theta(n^2) =>选项中最接近的答案是 O(n^2) 选F --------------- 第三小题 第一个for : theta( n^(log 3) ) 2 第二个for : theta( n*log n ) 2 theta( n^(log 3) ) + theta( n*log n ) 2 2 右边的成长比较快~ => O(n*log n) 2 选D ---------------(省略部分的字~好懒) 第四小题 第一个for : 2^(n/2) (成长较快) 选O(2^n) E 第二个for : n --------------- 第五小题 n^(1/2) 第一个for : (用刚刚的方法很难算) n^ 後续写不出来 改成T(n) = n * T( n^(1/2) ) = n * n^(1/2) * T( n^(1/4) ) = n * n^(1/2) * n^(1/4) * T( n^(1/8) ) = n * n^(1/2) * n^(1/4) * n^(1/8) * T( n^(1/16) ) = n * n^(1/2) *....... ( 1+(1/2) +(1/4)+ (1/8) +....+(1/n) ) =n^ 逼近 n^2 => O(n^2) 第二个for : (n^2)* log n 2 所以第二个成长较快 选H ㄧ起来讨论看看呗~ -- 学长学长!那边有飙车族 学长学长!那边刚好像有女生 学长学长!那边有人红灯右转 砍人 被压上车 ψQSWEET 鸽 ◥ 鸽 ◥ 鸽 ◥ 鸽 ◥ 鸽 ◥他妈的◤ 鸽 ◤◎ ◎ 喔~~ ◤︶ ︶ ◤◎ ◎ 喔~~ ◤︶ ︶ ◤◎ ◎ 拦下来呀!⊙ ⊙◥ ◥ ◤ ◥ █◤ ◥ ◤ ◥ 3◤╯ξ ◥ ◤没王法了◥皿 ◤ ◥ ◥◥ (哈欠)◤ ◥◤ ◥ ◥◥ (烟~) ◤ ◥ ◤￣ ◥ ◥◥是不是?!(◥ ◤ ◤) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.227.125.142 ※ 编辑: qazwsxee 来自: 61.227.125.142 (01/23 00:05) ※ 编辑: qazwsxee 来自: 61.227.125.142 (01/23 00:50)