找出具有混合线性和多项式时间的算法的时间复杂度
Finding the time complexity of an algorithm with mixed linear and polynomial times
我正在尝试根据经验计算出我编写的算法的复杂性。我在输入中有两个变量：数据集大小（矩阵的维度）和计算值的数量。
当我查看随值数量变化的复杂性时，它是线性的。
当我查看改变集合大小的复杂性时，它是多项式的。
我想估计复杂度系数。所以，
假设 T 是时间，v 值的数量和 s 大小，
很明显，时间与 v 的截距和斜率随着 s 的增加而增加
所以我将其建模为
T(v; 修正 s) = (a + b*v)*s
对于尺寸来说似乎是合理的
T(s; 修正 v) = s^c
如何将这两个放在一起？
T(v, s) = ?
如果我适合 log(T) = a + b*log(v) + c*log(s)
我非常适合 R 平方 = 0.9917
a = -5.5 p 值= 7.68e-16 ***
b = 1.7 p 值= 3.10e-12 ***
c = 2.1 p 值= < 2e-16 ***
我如何看待这些结果？它们表明时间在 v 中不是线性的
但是多项式 v^1.7（不是）。
任何人都可以让我走上正轨吗？
ps 我知道我应该能够从理论上计算复杂度，但我不是:-(
我找到了一个解决方案，也许不是最好的，但效果很好。
我意识到问题是线性关系的截距和斜率随集合大小而变化。所以，我使用了这个模型
T(v, s) = a(s) + b(s)*v
为了估计参数，首先我估计了每个集合的系数 a(s) 和 b(s)，然后在 s 上对它们进行回归。该关系仍然是多项式 [log(a(s)) = g + h*log(s)，类似于 b(s)]。意外的是，结果是b(s) = -a(s)，所以最后的分离函数是
T(v, s) = 10^k·s^2.1(v - 1)
其中 k 是一个常数，取决于测量单位。拟合与上面的多项式几乎相同。
感谢所有帮助过的人。
我正在尝试根据经验计算出我编写的算法的复杂性。我在输入中有两个变量：数据集大小（矩阵的维度）和计算值的数量。
当我查看随值数量变化的复杂性时，它是线性的。
当我查看改变集合大小的复杂性时，它是多项式的。
我想估计复杂度系数。所以， 假设 T 是时间，v 值的数量和 s 大小，
很明显，时间与 v 的截距和斜率随着 s 的增加而增加 所以我将其建模为
T(v; 修正 s) = (a + b*v)*s
对于尺寸来说似乎是合理的
T(s; 修正 v) = s^c
如何将这两个放在一起？
T(v, s) = ?
如果我适合 log(T) = a + b*log(v) + c*log(s)
我非常适合 R 平方 = 0.9917
a = -5.5 p 值= 7.68e-16 ***
b = 1.7 p 值= 3.10e-12 ***
c = 2.1 p 值= < 2e-16 ***
我如何看待这些结果？它们表明时间在 v 中不是线性的 但是多项式 v^1.7（不是）。
任何人都可以让我走上正轨吗？
ps 我知道我应该能够从理论上计算复杂度，但我不是:-(
我找到了一个解决方案，也许不是最好的，但效果很好。
我意识到问题是线性关系的截距和斜率随集合大小而变化。所以，我使用了这个模型
T(v, s) = a(s) + b(s)*v
为了估计参数，首先我估计了每个集合的系数 a(s) 和 b(s)，然后在 s 上对它们进行回归。该关系仍然是多项式 [log(a(s)) = g + h*log(s)，类似于 b(s)]。意外的是，结果是b(s) = -a(s)，所以最后的分离函数是
T(v, s) = 10^k·s^2.1(v - 1)
其中 k 是一个常数，取决于测量单位。拟合与上面的多项式几乎相同。
感谢所有帮助过的人。