确定具有两个参数的算法的 运行 时间
Determine the running time of an algorithm with two parameters
我实现了一种算法，该算法使用另外两种算法来计算图中的最短路径：Dijkstra 和 Bellman-Ford。根据这些算法的时间复杂度，我可以计算出我实现的运行时间，很容易给出代码。
现在，我想通过实验验证我的计算。具体来说，我想将 运行 时间绘制为输入大小的函数（我遵循 here 中描述的方法）。问题是我有两个参数——边数和顶点数。
我试图修复一个参数并更改另一个参数，但这种方法会产生两个图 - 一个用于不同数量的边，另一个用于不同数量的顶点。
这引出了我的问题 - 如何根据两个地块确定增长顺序？通常，如何通过实验确定具有多个参数的算法的 运行 时间复杂度？
我本来打算写自己的解释，但它不会比 this 好多少。
总的来说很难。
在单变量情况下，您通过实验测量 运行 时间的常用方法是，插入一个计数器，当您的数据结构执行基本（假设为 O(1)）操作时，该计数器会递增，然后取许多不同输入大小的数据，并将其绘制在 log-log 图上。即 log T 与 log N。如果 运行 时间的形式是 n^k，您应该会看到一条斜率 k 的直线，或者接近这个的东西。如果 运行 时间类似于 T(n) = n^{k log n} 之类的，那么您应该会看到一条抛物线。如果 T 在 n 中呈指数增长，您应该仍会看到指数增长。
执行此操作时，您只能希望获得有关最高阶项的信息——低阶项会被过滤掉，因为随着 n 变大，影响越来越小。
在两个变量的情况下，您可以尝试采用类似的方法——本质上，获取 3 维数据，绘制 log-log-log 图，并尝试为其拟合一个平面。
然而，只有在大多数制度中实际上只有一个主导术语时，这才会真正起作用。
假设我的实际函数是T(n, m) = n^4 + n^3 * m^3 + m^4。
当m = O(1)时，则T(n) = O(n^4)。
当 n = O(1) 时，则 T(n) = O(m^4)。
当n = m时，则T(n) = O(n^6).
在每个这些制度中，"slices" 沿着可能的 n、m 值的平面，不同的一项是主导项。
所以只取一些固定m的点和一些固定n的点是无法确定函数的。如果这样做，您将无法获得 n = m 的正确答案——您将无法发现 "middle" 这样的前导词。
我建议，当你有很多变量/复杂的数据结构时，预测渐近增长的最好方法是用铅笔和纸，并进行传统的算法分析。或者可能是一种混合方法。尝试将效率问题分解为不同的部分——如果您可以将问题分解为几个不同函数的总和或乘积，也许其中一些您可以抽象地确定，而一些您可以通过实验估计。
幸运的是，两个输入参数在 3D 散点图中仍然很容易可视化（第 3 维是测量的 运行 时间），您可以检查它是否看起来像一个平面（在 log-log-log比例）或者如果它是弯曲的。测量值的自然随机变化也在这里起作用。
在 Matlab 中，我通常会像这样计算 two-variable 函数的 least-squares 解（只是水平连接 x 和 y 的不同幂和组合，.* 是 element-wise 产品）：
x = log(parameter_x);
y = log(parameter_y);
% Find a least-squares fit
p = [x.^2, x.*y, y.^2, x, y, ones(length(x),1)] \ log(time)
然后这可用于估计 运行 次更大的问题实例，理想情况下，这些将通过实验确认，以了解拟合模型的工作原理。
这种方法也适用于更高的维度，但生成起来很乏味，也许有更通用的方法来实现这一点，这只是 work-around 我缺乏知识。
我实现了一种算法，该算法使用另外两种算法来计算图中的最短路径：Dijkstra 和 Bellman-Ford。根据这些算法的时间复杂度，我可以计算出我实现的运行时间，很容易给出代码。
现在，我想通过实验验证我的计算。具体来说，我想将 运行 时间绘制为输入大小的函数（我遵循 here 中描述的方法）。问题是我有两个参数——边数和顶点数。
我试图修复一个参数并更改另一个参数，但这种方法会产生两个图 - 一个用于不同数量的边，另一个用于不同数量的顶点。
这引出了我的问题 - 如何根据两个地块确定增长顺序？通常，如何通过实验确定具有多个参数的算法的 运行 时间复杂度？
我本来打算写自己的解释，但它不会比 this 好多少。
总的来说很难。
在单变量情况下，您通过实验测量 运行 时间的常用方法是，插入一个计数器，当您的数据结构执行基本（假设为 O(1)）操作时，该计数器会递增，然后取许多不同输入大小的数据，并将其绘制在 log-log 图上。即 log T 与 log N。如果 运行 时间的形式是 n^k，您应该会看到一条斜率 k 的直线，或者接近这个的东西。如果 运行 时间类似于 T(n) = n^{k log n} 之类的，那么您应该会看到一条抛物线。如果 T 在 n 中呈指数增长，您应该仍会看到指数增长。
执行此操作时，您只能希望获得有关最高阶项的信息——低阶项会被过滤掉，因为随着 n 变大，影响越来越小。
在两个变量的情况下，您可以尝试采用类似的方法——本质上，获取 3 维数据，绘制 log-log-log 图，并尝试为其拟合一个平面。
然而，只有在大多数制度中实际上只有一个主导术语时，这才会真正起作用。
假设我的实际函数是T(n, m) = n^4 + n^3 * m^3 + m^4。
当m = O(1)时，则T(n) = O(n^4)。
当 n = O(1) 时，则 T(n) = O(m^4)。
当n = m时，则T(n) = O(n^6).
在每个这些制度中，"slices" 沿着可能的 n、m 值的平面，不同的一项是主导项。
所以只取一些固定m的点和一些固定n的点是无法确定函数的。如果这样做，您将无法获得 n = m 的正确答案——您将无法发现 "middle" 这样的前导词。
我建议，当你有很多变量/复杂的数据结构时，预测渐近增长的最好方法是用铅笔和纸，并进行传统的算法分析。或者可能是一种混合方法。尝试将效率问题分解为不同的部分——如果您可以将问题分解为几个不同函数的总和或乘积，也许其中一些您可以抽象地确定，而一些您可以通过实验估计。
幸运的是，两个输入参数在 3D 散点图中仍然很容易可视化（第 3 维是测量的 运行 时间），您可以检查它是否看起来像一个平面（在 log-log-log比例）或者如果它是弯曲的。测量值的自然随机变化也在这里起作用。
在 Matlab 中，我通常会像这样计算 two-variable 函数的 least-squares 解（只是水平连接 x 和 y 的不同幂和组合，.* 是 element-wise 产品）：
x = log(parameter_x);
y = log(parameter_y);
% Find a least-squares fit
p = [x.^2, x.*y, y.^2, x, y, ones(length(x),1)] \ log(time)
然后这可用于估计 运行 次更大的问题实例，理想情况下，这些将通过实验确认，以了解拟合模型的工作原理。
这种方法也适用于更高的维度，但生成起来很乏味，也许有更通用的方法来实现这一点，这只是 work-around 我缺乏知识。