如何在良好的时间复杂度下遍历嵌套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)。

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