目录
一，id转换
1，id数组
如果一个数组有n个数，且其中包含了从0到n-1的所有数，则称之为id数组
2，基于id数组的重排双射
每一个id数组，都对应一种双射，把一个泛型数组进行重排。
如{3 0 1 2}，就是一个映射，{a b c d}->{d a b c}，可以理解为依次从一个泛型数组中按照id指引的位置取元素。
对于{8 5 6 7}，它需要基于{1 2 3 0}这个id数组进行重排，才能完成排序。
而对于{1 2 3 0}，它需要基于{3 0 1 2}这个id数组进行重排，才能完成排序。
ACM模板里面的VectorOpt::sortId函数，输入{8 5 6 7}，输出{1 2 3 0}，这个函数的功能就是对于每个泛型数组，求出它需要基于哪个id数组进行重排，才能完成排序。
因为比较函数中采用了id作为第二顺序关键字，所以它一定是稳定排序。
3，逆id数组
基于id数组的重排是双射，所以自然有逆映射，而逆映射一定是基于某个数组的重排，我们把这个数组，称为逆id数组。
神奇的是，任意一个id数组，基于它的逆进行id重排，就能完成排序。
也就是说，id数组S 和 sortId(S) 互为逆，上面的{1 2 3 0}和{3 0 1 2}就是一个例子。
一个id数组的逆，有可能是它自身，
如{1 4 3 2}需要基于{0 3 2 1}进行重排，才能完成排序，而{0 3 2 1}需要基于自身进行重排，才能完成排序，而{1 2 3 4}基于{0 3 2 1}进行重排。就会得到{1 4 3 2}
二，离散化
1，离散化
离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
（1）原数据：1,999,100000,15；处理后：1,3,4,2；
（2）原数据：{100,200}，{20,50000}，{1,400}；处理后：{3,4}，{2,6}，{1,5}；
PS：本文默认全部采用升序。
2，单射和双射
离散化其实是个映射，有2种表达方式。
（1）只关心数据的大小顺序，采用单射
离散化：{1,999,100000,15} -> {1,3,4,2}
（2）既关心数据的大小顺序，也关心数值本身，采用双射
离散化：{1,999,100000,15} -> {{1,3,4,2}，{1,15,999,100000}}
逆离散化： {{1,3,4,2}，{1,15,999,100000}} ->{1,999,100000,15}
3，模板代码
ACM模板里面的VectorOpt::sortId2函数，输入{8 5 6 7}，输出{3 0 1 2}，这就是离散化，我的模板是从0开始编号，用起来更方便。
离散化得到的，一定是一个id数组。
而sortId2的实现方式，就是sortId(sortId())，因为，排序后数组，基于原数组离散化得到的id数组进行重排，得到的就是原数组。
4，应用实例
解空间的离散化：持久化的代价是空间复杂度太高，为了均衡时间和空间，可以对持久空间做离散化。
5，小结
本章的变换可以认为是狭义离散化，而广义离散化包括id转换，即sortId和sortId2都可以认为是离散化。
他们之间的关系，可以称之为重排反演。
三，代数反演
前缀和运算，和差分运算，是一种完全互逆操作，可以称之为反演运算。
1，一维前缀差分
前缀和 {a}->{s}
s1=a1, s2=a1+a2, s3=a1+a2+a3......
差分 {s}->{a}
a1=s1, a2=s2-s1, a3=s3-s2......
除了初始项之外，每一个a都可以用2个s表示出来。
从集合映射的角度看，前缀和和差分是互为逆运算。
2，二维前缀差分
前缀和
差分
除了初始项之外，每一个a都可以用4个s表示出来。
如果是n维前缀差分，则每一个a都可以用2^n个s表示出来。
3，阿贝尔变换
四，组合反演
1，计数转换
{1,2,1,2,1,3,4,5} -> {<1,3>,<2,2>,<3,1>,<4,1>,<5,1>}
如果一个数据集的数值范围很大，但数据数量不多，那么计数转换其实也是一种广义的离散化。
2，平摊
{<1,3>,<2,2>,<3,1>,<4,1>,<5,1>}->{1,1,1,2,2,3,4,5}
很明显，计数转换和平摊并不是互逆的。
3，组合数求和反演
五，几何反演
1，几何反演
设在平面内给定一点O和常数k（k不等于零），对于平面内任意一点A，确定A′，使A′为直线OA上一点，并且有向线段OA与OA′满足OA·OA′=k，我们称这种变换是以O为反演中心，以k为反演幂的反演变换，简称反演。
当k>0时，有向线段OA与OA′同向，A与A′在反演极同侧，这种反演变换称为正幂反演，亦叫双曲线式反演变换。
当k<0时，有向线段OA与OA′反向，A与A′在反演极异侧，这种反演变换称为负幂反演，亦叫椭圆式反演变换。
2，圆和直线的反演
六，数论反演
七，谓词公式的反演和对偶
八，渗透网络的对偶
九，共轭
本章内容部分来自网友博客以及网友转载的原文凸优化问题、示性函数、共轭函数、对偶范数
1，共轭的类型
目前数学里面定义的共轭的类型包括但不限于以下内容：
- 共轭复数；
- 共轭根式；
- 共轭元素（场论）；
- 谐波共轭；
- 共轭转置；
- 共轭梯度法；
- 共轭先验/分布；
- 共轭线图（图论）；
- 共轭闭合（群论）；
- 等角共轭；
- 共轭点；
2，对偶和共轭的关系
对偶dual一定共轭conjugate，反之未必。
（集合中的2个元素）共轭conjugate，是说：一个元素a可以以1种确定的方式变成另外一个元素b。conjugate的本意，不是“一对”，而是“让2个东西能联结到一起”：
在整数加群中，“2”和“-2”关于零元共轭；在有理数域中，“2”和“1/2”关于幺元共轭；在复平面中，“1+i”和“1-i”关于实轴共轭；在向量空间中，向量（1,1）和向量（-2,2）关于纯数0共轭；在测度空间中，Lp空间和Lq关于代数运算（p + q = pq）共轭；……
（集合中的2个元素）对偶dual，是说：一个元素a可以以2种确定的方式变成另外一个元素b。dual的本意，也不是“一对”，而是“某件事的二重性、二元性、二象性、二择性”：
在整数环中，“2”可以共轭到“-2”，也可以通过乘以“-1”变成“-2”；在复平面中，“1+i”可以共轭到“1-i”，也可以旋转到“1-i”；在向量空间中，向量a可以经由某个双线性函数共轭到向量b，也可以经由特征矩阵变换到向量b；在满足Poincaré对偶的流形中，某个维度上的单形链既存在于同调群中，也存在于对偶的上同调群中；……
dual比conjugate厉害，是因为前者必须会玩2种游戏，而后者只要会1种游戏就行。即：后者是群group就行，而前者必须至少是环ring。
在很多场合（如：线性代数、赋范空间）不必区分dual和conjugate（二者是一回事）是因为这些场合天然自带“环ring”甚至“域field”。但在更一般的、只存在1种游戏的场合（如：测度空间、流形、复形），如果不另添加1种游戏进来，那就顶多只能玩conjugation了（duality没戏）。
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
