子序列是从另一个数列中选取一些项,并保持其原有顺序所得到的序列。选取时可以跳过某些项,但不能改变它们的先后顺序。在数学分析中,子序列用于研究收敛性、振荡和紧致性。在计算机科学和组合数学中,有限子序列用于描述从字符串、列表及其他有序数据中保持顺序的选取。
定义与记号
设 是取值于集合 的序列。无限子序列具有如下形式:
其中
为正整数。下标必须严格递增。因此,,且 。
等价地,若将序列视为函数 ,则子序列就是复合函数 ,其中 严格递增。这样的下标函数必然是单射函数,但仅有单射性还不够,因为它仍然允许改变顺序。
例如,对于
选取偶数下标可得
而选取平方数下标可得
所选的位置必须互不相同,但所选的值可以相同。如果一个序列中某个值出现无穷多次,那么它就有一个常值子序列。
对于有限序列 ,长度为 的子序列为
通常允许空序列作为有限子序列。每个序列都是它自身的子序列,而子序列的子序列仍是原序列的子序列。
与相关概念的区别
子序列不同于其他几种选取或重排方式。
- 子集:子集只记录成员归属,不记录位置或顺序。序列 和 的值构成相同的集合,但它们的子序列通常不同。
- 连续片段:连续片段保留的是连续位置上的项。在字符串术语中,这称为子串。每个子串都是子序列,但并非每个子序列都是子串。例如,“ace”是“abcde”的子序列,但不是它的子串。
- **重排:**重排会改变各项的顺序,通常通过对下标进行置换来实现。子序列则保持原有顺序。
- 子级数:无穷级数的子级数,是保留其中选定的项并按原有顺序求和得到的级数。所选的项构成原级数各项所成序列的子序列,但所得的部分和序列通常不是原部分和序列的子序列。
在分析学中,除非另有说明,“子序列”通常指无限子序列。在有限组合数学和算法中,它通常指有限子序列。
子序列与收敛性
极限的继承
如果一个序列收敛于 ,那么它的每个子序列都收敛于同一个 。在距离为 的度量空间中,根据极限的定义,有
事实上,对任意 ,原序列中所有充分靠后的项都满足 。由于 ,子序列中所有充分靠后的项也都满足同一不等式。
因此,删去开头有限项不会影响序列的收敛性,也不会改变其极限。
如果只知道存在一个收敛子序列,则逆命题不成立。例如,
不收敛,尽管
都是收敛子序列。在度量空间中,若两个子序列的极限不同,就能断定原序列发散。
子序列极限
子序列极限是指某个子序列的极限。在度量空间中, 是 的子序列极限,当且仅当以 为中心的每个开球都包含对应于无穷多个下标 的项 。
这里强调下标很重要。常值序列虽然只有一个取值,却仍有子序列极限。因此,子序列极限不一定是序列中不同取值所构成集合的聚点。
有界的实数序列收敛,当且仅当它恰有一个子序列极限。有界性不能直接省略:由下式定义的序列
只有一个有限的子序列极限 ,却不在 中收敛。
在度量空间中,有一个更一般的判别准则:
一个序列收敛于 ,当且仅当它的每个子序列都有一个进一步的子序列收敛于 。
如果原序列不收敛于 ,那么存在某个 ,使得可以选出一个子序列,其所有项到 的距离都至少为 。这个子序列的任何进一步的子序列都不可能收敛于 。
收敛子序列的存在性
博尔查诺–魏尔斯特拉斯定理指出,有限维欧几里得空间中的每个有界序列都有收敛子序列。原序列不必收敛;有界性保证可以按原有顺序选出一个收敛的子序列。
对于实数序列,一种标准证明利用了每个实数序列都有单调子序列这一事实。如果原序列有界,那么这个单调子序列也有界,因而收敛。
有限维这一假设至关重要。在无限维希尔伯特空间中,无限标准正交序列有界,但任意两个不同项之间的距离都是 。因此,它没有按范数收敛的子序列。
另一个相关事实涉及柯西序列:如果它有一个收敛于 的子序列,那么整个序列都收敛于 。柯西条件保证,所有充分靠后的项都与该收敛子序列中靠后的项足够接近。
列紧性
如果一个空间中的每个序列都有子序列收敛于该空间中的某一点,就称这个空间具有列紧性。
在度量空间中,列紧性等价于该空间是紧空间。因此, 的任一有界闭子集中的每个序列,都有子序列收敛于该子集内的某一点。
对于一般的拓扑空间,紧致性与列紧性未必等价。仅靠序列不足以刻画一般拓扑的所有方面;网和滤子提供了更广泛的收敛概念。
概率论中的子序列
子序列也将随机变量的不同收敛方式联系起来。如果
即 依概率收敛于 ,那么存在一个子序列满足
整个序列却未必几乎必然收敛。可以适当选取子序列,使相应定义的误差事件的概率之和有限,从而保证几乎必然只有有限多个这样的事件发生。
更准确地说,依概率收敛等价于:每个子序列都有一个进一步的子序列,几乎必然收敛于同一个随机变量 。仅存在一个几乎必然收敛的子序列并不足够。
有限子序列与算法
对于长度为 的序列,选取要保留的位置共有 种方式,其中包括不选取任何位置的情况。恰好保留 个位置的选法有
种,其中这一表达式是二项式系数。当序列中有重复元素时,不同的位置选法可能产生相同的值序列。因此, 计算的是位置选法的数量,而不一定是所得不同序列的数量。
若干重要的计算问题都与子序列有关:
- **子序列判定:**判断一个序列是否为另一个序列的子序列。从左到右扫描,将每个待匹配项与尚可使用的最早出现位置匹配,即可在线性时间内解决这一问题。
- **最长公共子序列:**寻找一个最长的序列,使其同时是两个给定序列的子序列。对于长度分别为 和 的输入,标准动态规划算法的时间复杂度为 。
- **最长递增子序列:**在一个元素可比较大小的序列中,寻找最长的严格递增子序列。基于比较的标准算法可在 时间内解决这一问题。
这些运行时间采用大O记号表示,并假设单个元素之间的比较可在常数时间内完成。相关应用包括文件比较、序列比对,以及识别数据中保持顺序的模式。对于递增子序列问题,必须区分严格递增与非递减,因为二者对重复值的处理不同。