这个 Python 代码片段的时间复杂度是多少？

Question

我正在尝试了解有关时间复杂度的更多信息，我读到字典 in 的复杂度为 O(1)。那么对于下面的函数，时间复杂度是O(n)吗？

def compare(n1, n2):
    x, y = 0, 0
    result = {}
    s1, s2 = str(n1), str(n2)
    for i in range(0, 4):
        result[s1[i]] = i
    for i in range(0, 4):
        if s2[i] in result:
            if result[s2[i]] == i:
                x += 1
            else:
                y += 1

Answer 1

让我们看看：你有 2 个循环，都执行字典操作和简单的算术运算。我们可以忽略它们，因为算术和字典在 O(1) 中工作。但是，由于你有 2 个 for 循环，你将遍历两倍的元素，因此我会说，你的时间复杂度是 O(2n)。时间完全只是一个花哨的词，描述了你的算法对 n 个元素将执行多少步。

Answer 2

"for 循环的复杂度通常为 O(n)" 这是错误的。

您的 for 循环的时间复杂度为 O(1)。它们不依赖于变量。它们有固定的迭代次数。您的代码中唯一的动态部分是 str(n1), str(n2)。这具有 O(log10(n1) + log10(n2)) 的时间复杂度。输入数字越大，转换所需的时间就越长。其余代码的时间复杂度为 O(1)。所以整个代码的时间复杂度为O(log10(n1) + log10(n2))

def compare(n1, n2):
    x, y = 0, 0 # O(1)
    result = {} # O(1)
    s1, s2 = str(n1), str(n2) # O(log10(n1) + log10(n2))
    for i in range(0, 4): # O(4) == O(1)
        result[s1[i]] = i # O(1)
    for i in range(0, 4): # O(1)
        if s2[i] in result: # O(1)
            if result[s2[i]] == i: # O(1)
                x += 1 # O(1)
            else:
                y += 1 # O(1)

这个 Python 代码片段的时间复杂度是多少？

What is the time complexity of this Python code snippet?

python

time-complexity