[理工] 幾題時間複雜度求算

[nO25948 (chenyuyan)]

https://i.imgur.com/AxNMAcO.jpg
https://i.imgur.com/2igbplh.jpg
https://i.imgur.com/QSOiORI.jpg
https://i.imgur.com/uFJQEVV.jpg
這是洪逸老師出的題目
想請教各位大大該如何解
第vi題不知道該怎麼下手
剩下的都是logn我想不到方法消掉

拜託各位了


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.214.142
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1511341074.A.562.html
推 barry70490: n用n-1下去帶
→ barry70490: T(n-1)=n-1+Σ(1>n-2)T(j)
推 barry70490: logx+logy=logxy
→ nO25948:  https://i.imgur.com/AkaS5iy.jpg
→ nO25948: 感謝b大幫忙，想問我哪邊做錯了
→ nO25948: 我有點笨，抱歉
→ TMDTMD2487: 第1個我是直接從T1往上推，然後看出來是2的次方減1
→ TMDTMD2487: 我想了一個好方法你把T(n)跟T(n-1)相減把sum的相都消
→ TMDTMD2487: 掉
→ TMDTMD2487: 第二個log相加等於裡面相乘
推 FRAXIS: 第四題 我以前有解過一個類似的  #1B1iNLea
→ TMDTMD2487: 第四個展開後會是n乘harmonic number(logn)
→ TMDTMD2487: harmonic H(n)複雜度θ(logn)所以H(logn)=θ(loglogn)
→ TMDTMD2487: H(n)=1+1/2+..+1/n 他的複雜度用積分可以輕易得證
→ nO25948:  https://i.imgur.com/RmRo9Tr.jpg
→ nO25948: 還是不太瞭解T大和F大的做法
→ nO25948: T(n)跟T(n-1)把sum的相消掉，這步不太清楚=_=
→ nO25948: 先謝謝你們，尤其是T大！！
→ nO25948: 我第四個卡在他log是二為底，沒辦法做成調和數列
→ nO25948: 第七題卡在log1*3*....*n
→ JKLee: https://i.imgur.com/OyhdCBO.jpg
→ JKLee: 我漏寫了T(1)=1
→ JKLee: To n大,第四個,你如何確定是1*3*..*n而不是2*4*..*n
→ JKLee: 我認為不論是哪個,皆小於log(n!),如果題目只要求漸近解BigO
推 TMDTMD2487: https://i.imgur.com/oXsqP9x.jpg
→ TMDTMD2487: 我寫的細一點了 不然第四應該就能變成最後了
→ TMDTMD2487: https://i.imgur.com/zf07v8E.jpg
→ TMDTMD2487: 除了第一題應該是問一般式其他的問複雜度就不用太care
→ TMDTMD2487: 那個log底要多少或是化減到T(1)反正那些都是常數
→ TMDTMD2487: 或是n能不能被2阿5阿整除這種問題就除非是要證明
→ TMDTMD2487: 才真的是要嚴謹的加個上界下界之類的不然一般就這樣了
推 leoone: 第一題用硬幹 幹的出來
→ leoone: T大算法還滿猛的XD
→ nO25948: 感謝T大！！讓我受益良多
→ nO25948: J大因為那時我是帶到T(n-(n-1)) 所以後面會是 logn-(n-3)
→ nO25948: +....
→ nO25948: 感謝你們的幫忙，今天課有點滿
→ nO25948: 拖到現在才能好好謝謝你們