Immutable.JS中deleteIn方法的时间复杂度是多少？

你的推测完全正确，当操作的嵌套结构每一层都为Immutable.Map、路径长度为P时，deleteIn的严格时间复杂度为 O(P log32 N)。

原理说明 #

• deleteIn的执行逻辑分为两个阶段：首先沿传入的路径逐层向下定位到目标键所在的父级Map，之后对父级Map执行单级delete操作完成删除。
• 每一层的定位操作本质是对当前层Map执行一次get，结合官方给出的Immutable.Map单级get/set/delete操作时间复杂度均为O(log32 N)的说明，每一步层级操作的时间复杂度为O(log32 N)，路径长度为P时总共有P次单级操作（P-1次get + 1次delete），整体复杂度自然为 O(P log32 N)。
• 补充说明：因为log32 N的实际数值非常小，例如当N达到百万量级时log32 N仅约等于4，所以多数业务场景下可以近似把deleteIn的复杂度看做O(P)，但严格的渐近时间复杂度仍然符合你推导的结论。

内容的提问来源于stack exchange，提问作者databasechaser