这是类型复杂度系列文章的第二篇,主要是几个常量之间的运算规则。
准确的计算规则满足常规的四则运算和乘方等简单规则。这些量级之间可以通过任意运算来组合。但涉及到化简可以有一些更加直接的规则。同时因为无穷量 无法直接与其他量进行运算,我们会给出比较大小的规则。
近似化简规则
当我们做近似化简的时候,低量级的符号可以被高量级吸收。即:
而对于无穷量 ,则可以吸收任意的量。即
极限情况下的化简规则*
在某些情况下,下面的规则适用:
在上面的规则中,因为 i 本身就表示的特定二进制位数的标量量级,这项化简符合其定义。
上式中,可以看成是特定长度()的特定量的组合,比如 ASCII 字符串,实际复杂度与 相当。
上面三条规则由于本身底数和指数都已经达到了一定量级,其所能表示的范围接近于 Top 类型。如序列化成长文本的 JSON 字符串等。
无穷大比较
除了常规的约简以外,无穷大无法参与跟其他量的计算。但不同系数和次数的无穷大数值,可以比大小。
首先,无穷大大于其他任意量。即
其次,同次数的无穷大量,系数大的数值大于系数小的。
不同次数的无穷大量,次数越大其数值越大,系数不影响:
次数和系数都相同的无穷大量,可以比较其余项的大小:
文章转载自轻技术,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。




