如何在很好的时间复杂度下遍历嵌套JSON对象？

Question

我有一个JSON对象，它有可能被嵌套几次，如下所示：

{
"type": "cars",
"nested1": {
    "nested2": {
        "name": "tesla",
        "nested3": {
            "name": "audi",
            "make": "q7",
            "nested4": {}
                   }
               }
           }
}

我希望能够遍历每个字段，检查它是否包含一个对象作为它的值，如果是这样的话，进入这个嵌套的，检查包含对象作为它的值的字段，依此类推……

我尝试过琐碎的方法，但时间复杂度变得非常糟糕。对于3个嵌套对象，它是O(n^3)，因为您必须遍历每个嵌套对象中的每个字段。

有没有什么数据结构可以给我更好的时间复杂度？

Answer 1

除非使用了其他信息，否则扫描结果将为O( Nₚ)，其中Nₚ是属性的数量。

在您的示例中，顶级对象具有2个属性，即下一个级别1、下一个级别2、第三个级别3和最终级别0。你需要访问8个属性，2+1+2+3+0。尽管8恰好是2³，但这并不会使算法O(N³)适用于任何有用的N，因为如果您有一个具有不同数量的属性或填充对象的级别多于或少于三个级别的示例，则该关系将断开。选择代表问题的N是正常的。如果您将JSON序列化为没有额外空格的文件，则查找空对象将变成对'{}‘的子字符串搜索，对于子字符串搜索，您将不会改进O(N)。

改进算法的唯一方法是使用一些额外的信息来避免访问每个属性；例如，如果您知道空对象只出现在第四层，那么您就不需要在该层或更深层查看对象中的属性。