[中學] 對數

[magic704226 (梅姬?沒雞?傻傻分不清楚)]

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://www.ptt.cc/bbs/Math/M.1676534698.A.F89.html
推 LPH66       : 題目的語意有點怪,不過就當指令數是 log_10(n) 來算
→ LPH66       : n 代 10000 進去, 然後算上一秒一百萬個指令
推 Refauth     : 第一句我就看不太懂XD
→ Refauth     : 題目是不是說：一個問題的複雜度是 O(log10n)
→ Refauth     : 且 電腦每秒鐘可以執行一百萬個指令
→ Refauth     : 如果某程序(？)的複雜度是一萬，請問電腦要跑多久？
→ Refauth     : 我覺得第一句話就把我給卡住了XD
有一個問題的時間複雜度為 O(log10n)
當執行1百萬條指令花了1秒
請問執行1萬條指令，需要多少時間?
※ 編輯: magic704226 (1.161.76.127 臺灣), 02/17/2023 01:42:20
推 LPH66       : 不是一萬條指令，是問題大小是一萬
推 sunev       : 題目有說是number of operation，但大O符號不是這樣
→ sunev       : 用的
推 LPH66       : 這就是我說題目的語意有點怪的地方
→ LPH66       : 但照他給出來的答案來看，出題者要考的只有簡單對數
→ LPH66       : (另一個出題者沒在管大O符號的原因是寫了底數出來
→ LPH66       :  因為對數底數不同只差常數倍，寫大O時不必寫底數
→ LPH66       :  但出題者還是寫了)
→ deepdish    : chatGPT會算 你可以問一下
→ deepdish    : https://i.imgur.com/Oh6ZWNi.png