0

对于更冗长的算法，确定时间复杂度（即 BigO）是一件很痛苦的事情。我的解决方案是使用参数 n 和 k 对算法的执行进行计时，并提出一个随 n 和 k 变化的函数（时间函数）。

我的数据如下所示：

n    k    executionTime
500  1    0.02
500  2    0.03
500  3    0.05
500  ...  ...
500  10   0.18
1000 1    0.08
...  ... ...
10000 1   9.8
...  ...  ...
10000 10  74.57

我一直在使用 stats R 包中的 lm() 函数。我不知道如何解释多元回归的输出，以确定最终的 Big-O。这是我的主要问题：如何将多变量回归的输出转化为对最佳 Big-O 时间复杂度评级的最终裁决？

这是 lm() 的输出：

Residuals:
    Min      1Q  Median      3Q     Max 
-14.943  -5.325  -1.916   3.681  31.475 

Coefficients:
          Estimate Std. Error t value Pr(>|t|)    
(Intercept) -2.130e+01  1.591e+00  -13.39   <2e-16 ***
n            4.080e-03  1.953e-04   20.89   <2e-16 ***
k            2.361e+00  1.960e-01   12.05   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 7.962 on 197 degrees of freedom
Multiple R-squared:  0.747, Adjusted R-squared:  0.7444 
F-statistic: 290.8 on 2 and 197 DF,  p-value: < 2.2e-16

这是 log(y) ~ log(n) + log(k) 的输出：

Residuals:
   Min      1Q  Median      3Q     Max 
-0.4445 -0.1136 -0.0253  0.1370  0.5007 

Coefficients:
         Estimate Std. Error t value Pr(>|t|)    
(Intercept) -16.80405    0.13749 -122.22   <2e-16 ***
log(n)        2.02321    0.01609  125.72   <2e-16 ***
log(k)        1.01216    0.01833   55.22   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.1803 on 197 degrees of freedom
Multiple R-squared:  0.9897,    Adjusted R-squared:  0.9896 
F-statistic:  9428 on 2 and 197 DF,  p-value: < 2.2e-16

这是主成分的输出，显示 n 和 k 都有助于多元模型的传播：

                      PC1(This is n)    PC2 (this is k)  PC3 (noise?)
Standard deviation     1.3654           1.0000           0.36840
Proportion of Variance 0.6214           0.3333           0.04524
Cumulative Proportion  0.6214           0.9548           1.00000
4

0 回答 0