algorithm - 计算 2^N 个函数的运行时间

Question

在家庭作业中，我被要求计算各种算法的运行时间。难倒我的部分是 2^N，因为 N 的大小太大了。

假设数据大小 N=1000 的 2^N 算法执行需要 5 秒，计算数据大小 {2000, 3000, 10000} 的运行时间

现在，根据指数除法的性质，2^2000/2^1000 = 2^1000。结果是在包含 2000 个项目的数据集上执行 5.071509e+301 秒。

如何为接下来的两个尺寸指定一个数字？ 2^2000 和 2^9000 在我使用的任何计算器中都返回无穷大。教授的提示是2^10近似于10^3，也就是说1024近似于1000。

Answer 1

时间复杂度的函数是f(N) = c * 2^N。

因为 f(1000) = 5，我们可以求解 c = 5/2¹⁰⁰⁰。

所以 f(N) = 5 * 2^{N - 1000}，而 f(k * 1000) = 5 * 2^{(k - 1)*1000}。

封锁似乎是计算 2ⁿ，所以我会指导您。

我将以您的一个示例来演示该方法:

2¹⁰⁰⁰ = 2^{10 * 100} = (2¹⁰)¹⁰⁰ ≈ (10 ³)¹⁰⁰ = 10^{3 * 100} = 10³⁰⁰ = 1e300

那是根据老师的提示，另一种更准确地计算数字的方法是:

2¹⁰⁰⁰ = 10^{1000 * log₁₀2} = 10^301.03 = 10^0.03 * 10³⁰¹ = 1.0715e301

(如你所见，更准确的方法将比近似方法的结果多10.7倍)