Re: [理工] 時間複雜度
※ 引述《alrightwill (歐萊威爾)》之銘言：
: Suppose a computer can solve a problem of size 100,000 in 15 hours.
: Assume that execution time is determined by CPU speed; i.e., no other
: constraint on performance.
: How large a problem can be solved in 15 hours by a computer that is 100
: times faster if the program's time complexity is
: 1. θ(n) 2. θ(n log n)
: 3. θ(n^2) 4. θ(n^3)
: 以前沒遇過這種題目, 不知如何把實際計算時間跟複雜度兜在一起
: 希望高手解答
首先題目意思就是要在同樣時間內解完
然後電腦快100倍 問可以解到多大的問題
我將這邊把電腦快100倍想成用原電腦跑100倍的時間
1. θ(n)
當size = s 要花 t 的時間跑
則size = ns 要花 nt 的時間跑
nt = 100t
=> n = 100
=> size = 100s
Ans: size = 10,000,000
2. θ(n log n)
當size = s 要花 t 的時間跑
則size = ns 要花 (n log n)t 的時間跑
(n log n)t = 100t
=> n log n = 100
=> n近似於57
=> size = 57s
Ans: size = 5,700,000
3. θ(n^2)
當size = s 要花 t 的時間跑
則size = ns 要花 (n^2)t 的時間跑
(n^2)t = 100t
=> n^2 = 100
=> n = 10
=> size = 10s
Ans: size = 1,000,000
4. θ(n^3)
當size = s 要花 t 的時間跑
則size = ns 要花 (n^3)t 的時間跑
(n^3)t = 100t
=> n^3 = 100
=> n 近似 4.64159
=> size = 4.64159
Ans: size = 464,159
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.45.139.44
推
03/15 03:53, , 1F
03/15 03:53, 1F
討論串 (同標題文章)
