根据给定时间，估计算法可以处理的输入大小

Question

如果我们知道算法/程序的时间复杂度是O(E log V)，并且有不同输入大小的执行时间数据，我将如何估计该程序V例如30秒可以完成的输入大小？

+------+---------+
|  V   |    T    |
+------+---------+
|   10 | 0,00018 |
|   20 | 0,00046 |
|   30 | 0,00091 |
|   40 | 0,0018  |
|   50 | 0,0020  |
|   60 | 0,0029  |
|   70 | 0,0038  |
|   80 | 0,0035  |
|   90 | 0,0069  |
|  100 | 0,008   |
|  200 | 0,037   |
|  300 | 0,093   |
|  500 | 0,35    |
|  750 | 0,95    |
| 1000 | 1,87    |
| 1500 | 6,26    |
| 2000 | 13,06   |
+------+---------+

Answer 1

线性近似的时间;让我们在R语言的帮助下完成它：

创建一个带有最后一个(即最精确(数字的csv 文件，例如：

V;T
200;0.016
300;0.047
500;0.13
750;0.42
1000;0.82
1500;2.8
2000;5.8    

并执行R脚本

df <- read.csv("C:\data.csv", header = TRUE, sep = ";")
df$LogV = log(df$V)
df$LogT = log(df$T)
m <- lm(df$logV ~ df$logT)
summary(m)

你会得到

Coefficients:
Estimate Std. Error t value Pr(>|t|)     
(Intercept) 6.941998   0.020574  337.42 4.34e-12  
df$LogT     0.390779   0.009129   42.81 1.31e-07 
--- Signif. codes:  0 ‘’ 0.001 ‘’ 0.01 ‘’ 0.05 ‘.’ 0.1 ‘ ’ 1
Residual standard error: 0.04787 on 5 degrees of freedom 
Multiple R-squared:  0.9973,    
Adjusted R-squared:  0.9967  
F-statistic:  1832 on 1 and 5 DF,  
p-value: 1.313e-07

相关性R相当不错，对应的公式是

LogV = 6.941998 + 0.390779 * LogT

或

V = Math.Exp(6.941998) * Math.Pow(T, 0.390779)

请注意，事实上，我们O(T**0.4)没有O(log(T));如果你测试

mLog <- lm(df$logV ~ df$T)

你会有更差的相关性。让我们比较现有值(Est. V)T的估计值，并将估计值与实际V进行比较：

V  (Est. V)   T
-----------------
10 (  25) 0.000
20 (  36) 0.000
30 (  48) 0.000
40 (  66) 0.001
50 (  66) 0.001
60 (  77) 0.001
70 (  86) 0.002
80 (  82) 0.002
90 ( 105) 0.003
100 ( 114) 0.004
200 ( 206) 0.016
300 ( 313) 0.047
500 ( 466) 0.130
750 ( 737) 0.420
1000 ( 958) 0.820
1500 (1547) 2.800
2000 (2057) 5.800

如果我们把T = 30我们得到V = 3909的估计，或者更好地说V ~ 4000

Answer 2

首先，您需要知道E如何取决于V。

如果没有有用的信息，请尝试将第二列值除以第一列的对数。

然后尝试通过某个函数近似结果值 - 似乎二次依赖性看起来很合理(并且 dence 图中的边数与顶点计数的平方成正比(。

找到E=G(V)后，使用结果公式获取V的数值，以达到 30 秒。例如(带二次函数(：

Time(V) = C*V*V*log(V)

估计C常数并找到函数Time(V)与秒水平线T=30相交的位置。