三层嵌套for循环遍历嵌套JS对象的时间复杂度咨询

你的判断是对的，这个遍历的时间复杂度是O(n)，其中n是所有元素的总数量。

虽然代码看起来是三层嵌套循环，但这和常规的三层独立循环（比如三个循环都遍历0到n）完全不同：

• 第一层循环遍历页面数量，每个页面对应第二层的分组；
• 第二层循环遍历当前页面下的分组，每个分组对应第三层的元素列表；
• 第三层循环只遍历当前分组里的元素，每个元素只会被访问一次。

整个遍历过程中，最内层代码的执行次数正好等于所有元素的总数，没有多余的重复操作。拿你给出的示例结构来说，总共有4个元素，最内层循环就会执行4次，总操作数和元素数量完全线性相关。

很多人容易把嵌套循环直接等同于高次复杂度，但那只适用于各层循环次数独立于数据结构的场景。而这里的三层循环是顺着嵌套结构的层级遍历，最终总操作数由叶子节点（元素）的数量决定，所以是线性时间复杂度O(n)。

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