解题思路与方法

给定长度为 $N$ 的时间序列

我们要按照如下定义计算第 $h$ 滞后的自相关系数 $\rho(h)$：

1. 序列均值

   $$\mu = \frac1N\sum_{t=0}^{N-1}X_t.$$

2. 方差（“平均平方偏差”）

   $$\sigma^2 = \frac1N\sum_{t=0}^{N-1}(X_t-\mu)^2.$$

3. 自相关系数
   对于 $0 \le h < N$，
   注意这里分子是对 $t=0\dots N-h-1$ 的累加和，并不再做额外的“平均”。
   当 $h\ge N$ 时，按题意定义 $\rho(h)=0$。

复杂度分析

• 时间复杂度：

  • 计算均值 $O(N)$
  • 计算方差 $O(N)$
  • 对每个 $h$ 累加 $\displaystyle\sum_{t=0}^{N-h-1}$ 需要 $O(N-h)$，总和$$\sum_{h=0}^{N-1}(N-h)=\frac{N(N+1)}2=O(N^2).$$

  因此总体 $O(N^2)$。

• 空间复杂度：
  需要存储输入数组和输出数组，各 $O(N)$。

代码实现

Python 实现

def autocorr(arr):
    n = len(arr)
    # 1. 计算均值
    mu = sum(arr) / n
    # 2. 计算方差（平均平方偏差）
    var = sum((x - mu) ** 2 for x in arr) / n
    res = []
    # 3. 依次计算每个滞后
    for h in range(n):
        s = 0.0
        # 累加 (X[t+h]-mu)*(X[t]-mu)
        for t in range(n - h):
            s += (arr[t + h] - mu) * (arr[t] - mu)
        # 除以 var（若 var==0 则定义 rho=0 避免除零）
        rho = s / var if var != 0 else 0.0
        # 保留三位小数
        res.append(round(rho, 1))
    return res

if __name__ == "__main__":
    data = list(map(float, input().split()))
    ac = autocorr(data)
    print(ac)

题目内容

给定一个时间序列数据，你的任务是计算并输出该序列的自相关函数。自相关函数的定义如下:

对于一个时间序列{$X_t$}，其自相关函数$\rho (h)$定义为:

$\rho(h)$=$\frac{E[(X_{t+h}-\mu )(X_t-\mu)]}{\sigma^2}$

其中，$E[·]$表示期望，$\mu$是序列的均值，$\sigma ^2$是序列的方差，$h$是滞后$(lag)$。

你需要写一个$Python$函数，接受一个由浮点数构成的列表作为输入，输出一个列表，列表中的第$i$个元素是输入序列的滞后$i$的自相关系数。你可以假设输入列表的长度至少为$2$，且所有的输入数据都是有效的。

输入描述

输入一行浮点数,空格间隔。

输出描述

直接输出列表

补充说明

1.你的程序需要能够处理任意长度的输入序列。

2.对于滞后大于序列长度的情况，自相关系数应被定义为$0$。

3.所有的输出应该保留一位小数。

样例1

输入

1.0 2.0 3.0 4.0

输出

[4.0, 1.0, -1.2, -1.8]