algorithm - 算法简介(第 1-1 章)

Question

只是为了好玩而阅读这本书，这不是作业。

但是我已经对第一个主要任务感到困惑:

1-1运行时间对比

对于下表中的每个函数 f(n) 和时间 t，确定在时间 t 可以解决的问题的最大规模 n，假设解决问题的算法需要 f(n)微秒。

这到底是什么意思？

下表显示了沿一个轴(1 秒、1 分钟、一小时等)的一堆时间，另一个轴显示了不同的 f(n)，例如 lg n、sqrt(n)、n 等.

我不知道如何填写矩阵，因为我看不懂这个问题。所以如果f(n) = lg n，它要求最大的n可以在例如1秒内解决，但是这个问题需要f(n) = lg n微秒才能解决？最后一部分是什么意思？我什至不知道如何设置方程式/比率来解决这个问题，因为我什至无法将问题的含义放在一起。

我的挂断在于“假设解决问题的算法需要 f(n) 微秒”这句话，因为我不知道这指的是什么。 what 算法解决what 问题的时间需要 f(n) 微秒？那么，如果我调用 f(100) 它将花费 lg 100 微秒？所以我需要找到一些 n，其中 f(n) = lg n 微秒 = 1 秒？

这是否意味着当 lg n 微秒 = 10^6 微秒时 lg n 微秒 = 1 秒，所以 n = 2^(10^6)？

Answer 1

对于每一次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 的最大值, 并填表。