作者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/cn.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