时间戳

首页 > 解决方案 > 在以下代码中声明 dict 和数组的空间复杂度是多少？

python - 在以下代码中声明 dict 和数组的空间复杂度是多少？

问题描述

由于我声明了字典和数组，以下代码的空间复杂度是多少？

--> 根据我的假设，我会说 0(n + m) 因为 dict 占用 o(n) 空间，而堆栈也占用 o(m) 空间。我对么？

hash_brackets = {
    "(":")",
    "{":"}",
    "[":"]"
}
        
stack = []
for bracket in s:
            
    if bracket in hash_brackets:
        stack.append(hash_brackets[bracket])
            
    elif len(stack) > 0 and bracket == stack[-1]:
        stack.pop()
    else:
        return False
        
return len(stack) == 0

标签： pythonalgorithm

解决方案

前言

发布的代码无效且不完整，但它看起来像检查括号是否平衡的函数体。填补空白，我得到了这个：

def balanced_brackets(s: str) -> bool:
    hash_brackets = {
        "(": ")",
        "{": "}",
        "[": "]"
    }

    stack = []
    for bracket in s:
        if bracket in hash_brackets:
            stack.append(hash_brackets[bracket])
        elif len(stack) > 0 and bracket == stack[-1]:
            stack.pop()
        else:
            return False
    return len(stack) == 0

其次，我假设您要问的是大 O 复杂性，而不是小 O。

dict 是 O(1) 因为你不添加它。

该列表是 O(n)，因为您添加到它。请记住，big-O 是一个上限，在这种情况下，这意味着其中的每个字符s都是一个开括号。

推荐阅读