python的len()函数的时间复杂度是多少？

Question

面试官问我python的len()函数的时间复杂度是多少？

请详细解释一下答案。这 3 种情况的时间复杂度是否相同？

打印（len（'abcdefghij'））

打印（len（[1,2,3,4,5,6,7,8,9,10]））

打印(len((1,2,3,4,5,6,7,8,9,10)))

Answer 1

len()

的时间复杂度

Python的

len()

函数的时间复杂度为O(1)，也称为常数时间复杂度。这种效率归功于 Python 实现其数据结构的方式：

1. 字符串：在 Python 中创建字符串时，字符串的长度将作为字符串元数据的一部分进行存储和更新。因此，当您对字符串调用

   len()

   时，Python 只需检索预先计算的长度，而不需要计算每个字符。示例：

   len('abcdefghij')

   .

2. 列表：与字符串类似，列表的长度存储为列表元数据的一部分。当列表被修改（添加或删除元素）时，Python 会更新此存储的长度。因此，在列表上调用

   len()

   并不涉及迭代其元素。示例：

   len([1,2,3,4,5,6,7,8,9,10])

   .

3. 元组：Python 中的元组是不可变的，这意味着它们的大小一旦创建就不会改变。就像字符串和列表一样，元组的长度被存储并且易于访问，使得

   len()

   成为常数时间操作。示例：

   len((1,2,3,4,5,6,7,8,9,10))

   .

跨数据类型的一致性

len()

函数的时间复杂度在这些不同的数据类型（字符串、列表和元组）中是一致的，因为在每种情况下，Python 都会将长度作为对象元数据的一部分进行维护。因此，无论数据结构的大小如何，

len()

始终会在恒定时间 O(1) 内执行，这使得它对于任何长度的字符串、列表或元组都非常高效。