比较子列表时如何找到时间复杂度？

Question

def check_lists(list_1, list_2):
    if list_1 == None or list_2 == None:
        return None
    for i in range(len(list_1)):
        if list_1[i] != list_2[i]:
            return None
    return list_1

def check_sublists(lst, fir, la):
    mid = (la + fir) // 2
    if (la - fir == 0):
        return lst[fir]  
    if (la - fir == 1):
        return check_lists(lst[fir], lst[la])
    return check_lists(check_sublists(lst, fir, mid), check_sublists(lst, mid + 1, la))

lst = [[1, 2, 3], [1, 2, 3], [1, 2, 6], [1, 2, 3]]

result = check_sublists(lst, 0, len(lst) - 1)
print(result)

因此函数

check_lists

使用 for 循环比较两个列表，因此它的时间复杂度为 O(k)，在这种情况下它将用于比较子列表。重点是检查所有子列表是否相同。函数

check_sublists

是实际递归比较其子列表的函数。通过使用主定理，我得到 a=b=2。最大子列表大小也由 k 给出。嵌套列表大小为n。我应该用这两个变量来描述时间复杂度。但使用主定理我陷入困境，因为 f(n) 取决于 k。我的意思是非递归部分是 k + 常数。我该怎么做？

Answer 1

当顶级列表的所有元素都相等时，最坏的情况就会出现，因为

None

中的

check_lists

条件永远不会成立。

当子列表只有 1 或 2 个元素时，就会出现递归的基本情况。在后一种情况下，

check_lists

比较顶级列表中两个相邻元素。

递归情况也称为

check_lists

，从左分区中取出一个元素，从右分区中取出一个元素。选择/返回这些分区中的哪个元素并不重要：当我们返回一个元素时，这意味着它们在该分区中都是相同的，所以我们可以想象它是来自左分区和右分区最左边的元素。 如果我们以这种方式考虑元素，我们可以看到顶级列表的所有

相邻

元素都会受到check_lists的调用，并且只调用一次。在 𝑛 元素列表中，有 𝑛−1 个相邻对，因此我们可以得出结论，恰好进行了 𝑛−1 次

check_lists

调用。由于每次调用的最坏情况时间复杂度为 O(𝑘)，因此总体时间复杂度为 O(𝑛𝑘)。