如何在嵌套字典中根据值找对应键并优化O(n³)时间复杂度？

Hey there! Let's tackle your problem step by step—first, we'll figure out how to trace back the keys "avgresptime" and "Appdynamics" for the value "art", then we'll optimize that O(n³) approach to something much more efficient.

Example Nested Structure #

First, let's use a sample nested dictionary that matches your description to make things concrete:

nested_dict = {
    "Appdynamics": {
        "avgresptime": ["art", 123, "response_metric"],
        "error_rate": ["err", 456]
    },
    "Prometheus": {
        "cpu_usage": ["cpu", 789]
    }
}

Finding the Key Path to "art" #

The core idea is to traverse the nested structure (dictionaries and lists) while keeping track of the path of keys we've taken. When we hit the value "art", we can return that path to get your desired keys.

Recursive Approach #

This is straightforward for moderate-sized structures:

def find_target_path(data, target, current_path=None):
    if current_path is None:
        current_path = []
    
    # Traverse dictionaries
    if isinstance(data, dict):
        for key, value in data.items():
            updated_path = current_path + [key]
            result = find_target_path(value, target, updated_path)
            if result is not None:
                return result
    # Traverse lists
    elif isinstance(data, list):
        for item in data:
            if item == target:
                return current_path
            # Check for nested structures inside the list
            result = find_target_path(item, target, current_path)
            if result is not None:
                return result
    # Check if current value is the target (for non-collection types)
    elif data == target:
        return current_path
    
    # Target not found in this branch
    return None

# Usage
target = "art"
path = find_target_path(nested_dict, target)

if path:
    print(f"Full path to 'art': {path}")
    print(f"Upper level key: {path[0]}")  # Outputs "Appdynamics"
    print(f"List-associated key: {path[1]}")  # Outputs "avgresptime"
else:
    print(f"'{target}' not found in the structure")

Iterative Approach (Avoids Recursion Limits) #

For very deep nested structures, an iterative DFS approach is safer to avoid stack overflow:

def find_target_path_iterative(data, target):
    # Stack stores tuples of (current_element, current_path)
    stack = [(data, [])]
    
    while stack:
        current, path = stack.pop()
        
        if isinstance(current, dict):
            for key, value in current.items():
                stack.append((value, path + [key]))
        elif isinstance(current, list):
            for item in current:
                if item == target:
                    return path
                stack.append((item, path))
        elif current == target:
            return path
    
    return None

# Usage is the same as the recursive version
path = find_target_path_iterative(nested_dict, target)

Optimizing Time Complexity #

Your original O(n³) approach likely comes from nested loops over the dictionary layers and list. The methods above run in O(N) time, where N is the total number of elements in the entire nested structure (including all dictionary key-value pairs, list items, and nested sub-structures). This is optimal because we only need to visit each element once to check for the target.

Key Takeaways #

• The path returned by the functions gives you the exact hierarchy of keys leading to the list containing "art"—in your case, ["Appdynamics", "avgresptime"].
• Both recursive and iterative approaches are far more efficient than O(n³), with linear time complexity relative to the size of your data.

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