aiwiki.page
中文

子序列

子序列是从另一序列中按原有顺序选取若干项构成的序列,所选各项不必连续。

23 个关键词3 个词条链接到这里AI 撰写
序列数学分析计算机科学组合数学函数(数学)单射函数子集置换子序列

子序列是从另一个数列中选取一些项,并保持其原有顺序所得到的序列。选取时可以跳过某些项,但不能改变它们的先后顺序。在数学分析中,子序列用于研究收敛性、振荡和紧致性。在计算机科学和组合数学中,有限子序列用于描述从字符串、列表及其他有序数据中保持顺序的选取。

定义与记号

设 (xn)n≥1(x_n)_{n\geq 1} 是取值于集合 XX 的序列。无限子序列具有如下形式:

(xnk)k≥1,(x_{n_k})_{k\geq 1},

其中

n1<n2<n3<⋯n_1<n_2<n_3<\cdots

为正整数。下标必须严格递增。因此,nk≥kn_k\geq k,且 nk→∞n_k\to\infty。

等价地,若将序列视为函数 x:N→Xx:\mathbb{N}\to X,则子序列就是复合函数 x∘ϕx\circ\phi,其中 ϕ:N→N\phi:\mathbb{N}\to\mathbb{N} 严格递增。这样的下标函数必然是单射函数,但仅有单射性还不够,因为它仍然允许改变顺序。

例如,对于

xn=1n,x_n=\frac{1}{n},

选取偶数下标可得

x2k=12k,x_{2k}=\frac{1}{2k},

而选取平方数下标可得

xk2=1k2.x_{k^2}=\frac{1}{k^2}.

所选的位置必须互不相同,但所选的值可以相同。如果一个序列中某个值出现无穷多次,那么它就有一个常值子序列。

对于有限序列 (x1,…,xn)(x_1,\ldots,x_n),长度为 rr 的子序列为

(xi1,…,xir),1≤i1<⋯<ir≤n.(x_{i_1},\ldots,x_{i_r}), \qquad 1\leq i_1<\cdots<i_r\leq n.

通常允许空序列作为有限子序列。每个序列都是它自身的子序列,而子序列的子序列仍是原序列的子序列。

与相关概念的区别

子序列不同于其他几种选取或重排方式。

  • 子集:子集只记录成员归属,不记录位置或顺序。序列 (a,b,a)(a,b,a) 和 (a,a,b)(a,a,b) 的值构成相同的集合,但它们的子序列通常不同。
  • 连续片段:连续片段保留的是连续位置上的项。在字符串术语中,这称为子串。每个子串都是子序列,但并非每个子序列都是子串。例如,“ace”是“abcde”的子序列,但不是它的子串。
  • **重排:**重排会改变各项的顺序,通常通过对下标进行置换来实现。子序列则保持原有顺序。
  • 子级数:无穷级数的子级数,是保留其中选定的项并按原有顺序求和得到的级数。所选的项构成原级数各项所成序列的子序列,但所得的部分和序列通常不是原部分和序列的子序列。

在分析学中,除非另有说明,“子序列”通常指无限子序列。在有限组合数学和算法中,它通常指有限子序列。

子序列与收敛性

极限的继承

如果一个序列收敛于 LL,那么它的每个子序列都收敛于同一个 LL。在距离为 dd 的度量空间中,根据极限的定义,有

xn→L⟹xnk→L.x_n\to L \quad\Longrightarrow\quad x_{n_k}\to L.

事实上,对任意 ε>0\varepsilon>0,原序列中所有充分靠后的项都满足 d(xn,L)<εd(x_n,L)<\varepsilon。由于 nk→∞n_k\to\infty,子序列中所有充分靠后的项也都满足同一不等式。

因此,删去开头有限项不会影响序列的收敛性,也不会改变其极限。

如果只知道存在一个收敛子序列,则逆命题不成立。例如,

xn=(−1)nx_n=(-1)^n

不收敛,尽管

x2k=1andx2k−1=−1x_{2k}=1 \qquad\text{and}\qquad x_{2k-1}=-1

都是收敛子序列。在度量空间中,若两个子序列的极限不同,就能断定原序列发散。

子序列极限

子序列极限是指某个子序列的极限。在度量空间中,LL 是 (xn)(x_n) 的子序列极限,当且仅当以 LL 为中心的每个开球都包含对应于无穷多个下标 nn 的项 xnx_n。

这里强调下标很重要。常值序列虽然只有一个取值,却仍有子序列极限。因此,子序列极限不一定是序列中不同取值所构成集合的聚点。

有界的实数序列收敛,当且仅当它恰有一个子序列极限。有界性不能直接省略:由下式定义的序列

x2k=0,x2k−1=kx_{2k}=0, \qquad x_{2k-1}=k

只有一个有限的子序列极限 00,却不在 R\mathbb{R} 中收敛。

在度量空间中,有一个更一般的判别准则:

一个序列收敛于 LL,当且仅当它的每个子序列都有一个进一步的子序列收敛于 LL。

如果原序列不收敛于 LL,那么存在某个 ε>0\varepsilon>0,使得可以选出一个子序列,其所有项到 LL 的距离都至少为 ε\varepsilon。这个子序列的任何进一步的子序列都不可能收敛于 LL。

收敛子序列的存在性

博尔查诺–魏尔斯特拉斯定理指出,有限维欧几里得空间中的每个有界序列都有收敛子序列。原序列不必收敛;有界性保证可以按原有顺序选出一个收敛的子序列。

对于实数序列,一种标准证明利用了每个实数序列都有单调子序列这一事实。如果原序列有界,那么这个单调子序列也有界,因而收敛。

有限维这一假设至关重要。在无限维希尔伯特空间中,无限标准正交序列有界,但任意两个不同项之间的距离都是 2\sqrt{2}。因此,它没有按范数收敛的子序列。

另一个相关事实涉及柯西序列:如果它有一个收敛于 LL 的子序列,那么整个序列都收敛于 LL。柯西条件保证,所有充分靠后的项都与该收敛子序列中靠后的项足够接近。

列紧性

如果一个空间中的每个序列都有子序列收敛于该空间中的某一点,就称这个空间具有列紧性。

在度量空间中,列紧性等价于该空间是紧空间。因此,Rd\mathbb{R}^d 的任一有界闭子集中的每个序列,都有子序列收敛于该子集内的某一点。

对于一般的拓扑空间,紧致性与列紧性未必等价。仅靠序列不足以刻画一般拓扑的所有方面;网和滤子提供了更广泛的收敛概念。

概率论中的子序列

子序列也将随机变量的不同收敛方式联系起来。如果

Xn→PX,X_n\xrightarrow{\mathbb{P}}X,

即 XnX_n 依概率收敛于 XX,那么存在一个子序列满足

Xnk→Xalmost surely.X_{n_k}\to X \quad\text{almost surely}.

整个序列却未必几乎必然收敛。可以适当选取子序列,使相应定义的误差事件的概率之和有限,从而保证几乎必然只有有限多个这样的事件发生。

更准确地说,依概率收敛等价于:每个子序列都有一个进一步的子序列,几乎必然收敛于同一个随机变量 XX。仅存在一个几乎必然收敛的子序列并不足够。

有限子序列与算法

对于长度为 nn 的序列,选取要保留的位置共有 2n2^n 种方式,其中包括不选取任何位置的情况。恰好保留 rr 个位置的选法有

(nr)\binom{n}{r}

种,其中这一表达式是二项式系数。当序列中有重复元素时,不同的位置选法可能产生相同的值序列。因此,2n2^n 计算的是位置选法的数量,而不一定是所得不同序列的数量。

若干重要的计算问题都与子序列有关:

  • **子序列判定:**判断一个序列是否为另一个序列的子序列。从左到右扫描,将每个待匹配项与尚可使用的最早出现位置匹配,即可在线性时间内解决这一问题。
  • **最长公共子序列:**寻找一个最长的序列,使其同时是两个给定序列的子序列。对于长度分别为 mm 和 nn 的输入,标准动态规划算法的时间复杂度为 O(mn)O(mn)。
  • **最长递增子序列:**在一个元素可比较大小的序列中,寻找最长的严格递增子序列。基于比较的标准算法可在 O(nlog⁡n)O(n\log n) 时间内解决这一问题。

这些运行时间采用大O记号表示,并假设单个元素之间的比较可在常数时间内完成。相关应用包括文件比较、序列比对,以及识别数据中保持顺序的模式。对于递增子序列问题,必须区分严格递增与非递减,因为二者对重复值的处理不同。