只是为了好玩而读这本书,这不是功课.
但是我对第一个主要任务感到困惑:
1-1运行时间比较
对于下表中的每个函数f(n)和时间t,确定可以在时间t中求解的问题的最大尺寸n,假设解决问题的算法花费f(n)微秒.
这甚至意味着什么？
下一个表显示沿一个轴(1秒,1分钟,1小时等)的一堆时间,另一个轴显示不同的f(n),例如lg n,sqrt(n),n等.
我不知道如何填写矩阵,因为我无法理解这个问题.因此,如果f(n)= lg n,则询问可以求解的最大n,例如1秒,但问题需要f(n)= lg n微秒才能解决？这最后一部分甚至意味着什么？我甚至不知道如何设置方程/比率来解决这个问题,因为我甚至无法将问题的含义放在一起.
我的挂断在句子"假设解决问题的算法需要f(n)微秒",因为我不知道这是指什么.该时间什么解决算法有什么问题需要F(N)微秒？所以如果我调用f(100)它将需要lg 100微秒？所以我需要找到一些n,其中f(n)= lg n微秒= 1秒？
当lg n微秒= 10 ^ 6微秒时,这是否意味着lg n微秒= 1秒,所以n = 2 ^(10 ^ 6)？
对于每一个时间T,每一个功能f(n),您需要找到最大的整数n使得f(n) <= T
例如,f(n) = n^2, T=1Sec = 1000 ms:
n^2 <= 1000
n <= sqrt(1000)
n <= ~31.63 <- not an integer
n <= 31
给定任何函数f(n),并且有时间T,您需要同样找到最大值n,并填写表格.