更新时间:2024-08-09 16:21
形式上,一个在集合S上的二元运算 被称之为可结合的若其满足下面的结合律:
。
运算的顺序并不会影响到表示式的值,且可证明这在含有“任意”多个 运算的表示式之下也依然是成立的。因此,当 是可结合的时,运算的顺序可以不需要去规范而不会使其意义不清,所以可以省略掉括号而简单写成:
不过,需要记住的是,改变运算的顺序并不包含或允许以移动表示式中的算子来改变其真实的运算。
交:(A∩B)∩C=A∩(B∩C)
并:(A∪B)∪C=A∪(B∪C)
矩阵乘法满足结合律。
一个A x B的矩阵乘以一个B x C的矩阵将得到一个A x C的矩阵,时间复杂度为A x B x C。
一些可结合的运算的例子如下。
复数和四元数的加法与乘法是可结合的。八元数的加法也是可结合的,但其乘法则是不可结合的。
因为线性变换是个可表示成矩阵的函数,其中的函数复合则可以用矩阵乘法来表示,立即可知矩阵乘法为可结合的。
若M是某个集合且S为所有从M映射至M的函数所组成的集合,则在S上的函数复合的运算是可结合的:
。
更一般性地,给定四个集合M、N、P和Q,且 、 ,则
和前面一样。简单地说,映射的复合总会是可结合的。
给定一个有三个元素A、B和C的集合,其运算如下:
是可结合的。不过,此运算不是可交换的。
一个在集合S上的二元运算*若不满足结合律,则称之为不可结合的。表示成符号即为:
。
在此一运算下,运算的顺序是有影响的。减法、除法和幂都是不可结合运算的简单例子:
一般,当不可结合运算在一个表示出现多于一次时,括号就必须被使用来表示其运算顺序。不过,数学家会对若干常见的不可结合运算采用一种特别的运算顺序的规则。这单纯只是个为了减少括号的语法约定。