作者magic704226 (梅姬?沒雞?傻傻分不清楚)
看板Math
標題[中學] 對數
時間Thu Feb 16 16:04:55 2023
The complexity of a problem is O(log10n) and the computer
executes 1 million instructions per second.
How long does it take to run the program if the number
of operations is 10,000?
a. 1 microsecond
b. 2 microseconds
c. 3 microseconds
d. 4 microseconds
答案是 4 microsecond
令 log(k*10*1000000)
k=1/(10^6)
10000代入之後就卡住了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.104.136.224 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1676534698.A.F89.html
1F：推 LPH66 : 題目的語意有點怪,不過就當指令數是 log_10(n) 來算 02/16 18:06
2F：→ LPH66 : n 代 10000 進去, 然後算上一秒一百萬個指令 02/16 18:07
3F：推 Refauth : 第一句我就看不太懂XD 02/16 22:58
4F：→ Refauth : 題目是不是說：一個問題的複雜度是 O(log10n) 02/16 22:59
5F：→ Refauth : 且 電腦每秒鐘可以執行一百萬個指令 02/16 22:59
6F：→ Refauth : 如果某程序(？)的複雜度是一萬，請問電腦要跑多久？ 02/16 23:01
7F：→ Refauth : 我覺得第一句話就把我給卡住了XD 02/16 23:01
有一個問題的時間複雜度為 O(log10n)
當執行1百萬條指令花了1秒
請問執行1萬條指令，需要多少時間?
※ 編輯: magic704226 (1.161.76.127 臺灣), 02/17/2023 01:42:20
8F：推 LPH66 : 不是一萬條指令，是問題大小是一萬 02/18 11:01
9F：推 sunev : 題目有說是number of operation，但大O符號不是這樣 02/18 11:11
10F：→ sunev : 用的 02/18 11:11
11F：推 LPH66 : 這就是我說題目的語意有點怪的地方 02/18 15:50
12F：→ LPH66 : 但照他給出來的答案來看，出題者要考的只有簡單對數 02/18 15:51
13F：→ LPH66 : (另一個出題者沒在管大O符號的原因是寫了底數出來 02/18 15:51
14F：→ LPH66 : 因為對數底數不同只差常數倍，寫大O時不必寫底數 02/18 15:52
15F：→ LPH66 : 但出題者還是寫了) 02/18 15:53
16F：→ deepdish : chatGPT會算 你可以問一下 03/10 18:01