r - R 中 arima() 函数的计算复杂度是多少？

Question

如果我的时间序列有 n成员(member)和我想合身 ARIMA(1,0,1)模型，大的复杂度是多少 O符号？

在下面的例子中，我需要知道第二行代码的复杂性:

series <- arima.sim(list(order=c(1,0,1), ar=.9, ma=-.5), n=1000)
result <- arima(series, order=c(1,0,1))

谢谢。

Answer 1

是O(n)复杂。一个故事？见下文。

正如我在评论中所说，我们可以通过回归模型来衡量它。作为玩具演示，请考虑以下数据收集和回归过程。

我们首先定义一个函数来测量 ARMA(1,1) 的模型拟合时间模型(或 ARIMA(1,0,1))。 (请注意，我在这里使用的是基本的 system.time()。您可以考虑使用来自 microbenchmark() 包中的 microbenchmark 。但在下面，我将使用相当大的 n ，以降低时间测量的灵敏度。)

t_arma <- function(N) {
  series <- arima.sim(list(order=c(1,0,1), ar=.9, ma=-.5), n=N)
  as.numeric((system.time(arima(series, order=c(1,0,1)))))[3]
  }

我们需要收集，比如说 100 个数据。我们尝试 100 个越来越大的 n ，并测量模型拟合时间 t .

k <- 100; t <- numeric(k)
n <- seq(20000, by = 1000, length = k)  ## start from n = 20000 (big enough)
for (i in 1:k) t[i] <- t_arma(n[i])

现在，如果我们假设复杂度是: a * (n ^ b) , 或 O(n ^ b) ，我们可以估算 a , b通过回归模型:

log(t) ~ log(a) + b * log(n)

我们对斜率估计特别感兴趣: b .

所以让我们打电话 lm()

fit <- lm(log(t) ~ log(n))

#Coefficients:
#(Intercept)       log(n)  
#    -9.2185       0.8646  

我们也可以画出 log(n)的散点图。诉 log(t) ，以及拟合线:

plot(log(n), log(t), main = "scatter plot")
lines(log(n), fit$fitted, col = 2, lwd = 2)

一开始有一些异常值，因此斜率低于应有的水平。我们现在考虑去除异常值并重新拟合模型以获得稳健性。

异常值具有较大的残差。我们来看一下:

plot(fit$resi, main = "residuals")

我们可以标记并删除这些异常值。看起来像 0.5是一个足够好的阈值来过滤这些异常值。

exclude <- fit$resi > 0.5
n <- n[!exclude]
t <- t[!exclude]

现在我们重新拟合线性模型并绘制:

robust_fit <- lm(log(t) ~ log(n))

#Coefficients:
#(Intercept)       log(n)  
#    -11.197        1.039  

plot(log(n), log(t), main = "scatter plot (outliers removed)")
lines(log(n), robust_fit$fitted, col = 2, lwd = 2)

哇，太好了，我们是金色的!斜率估计值为 1。所以 O(n)复杂是有道理的!