检查列表的大小是线性的吗？
Is checking the size of a list linear?
我在网上看到很多回答说检查列表的大小是常数时间，但我不明白为什么。
我的理解是列表不存储在连续的内存块中（如数组），这意味着如果不先遍历每个列表，就无法获取列表的大小（最后一个元素索引 + 1）元素.
想法？
在不保留手头位置的情况下查找列表长度的唯一方法是遍历列表。它们不存储在块中，因此需要迭代直到到达最后一个元素。因此时间复杂度为 O(n)。当然，如果您存储一个保存长度的变量并在每次添加元素时递增它（并在删除元素时递减），则不需要遍历它，这将使它保持不变，因为您只需要第一个元素，或从存储长度的任何地方检索数据。也许可以使用根元素来保存长度，因此无需循环遍历它来获取长度。简而言之，你是对的。人们可能会说常量的原因是它是否预先存储。
I've seen many answers online saying that checking the size of a list is constant time.
这个谬误可能源于 Python 语言的一个根本缺陷：数组在 Python 中被称为 lists。随着 Python 越来越受欢迎，list 这个词变得模棱两可。
计算链表的长度是一个 O(n) 操作，除非长度已单独存储并妥善维护。
如果大小与数组一起存储，则检索数组的大小是在常数时间内执行的，如 Python 中的情况，因此 a=[1,2,3]; len(a) 确实非常快。
如果必须扫描数组以查找终止值（例如空指针或空字节），则计算数组的长度可能是一个 O(n) 操作。因此，C 中的 strlen() 计算 C 字符串中的字节数（char 的空终止数组）以线性时间运行。
我在网上看到很多回答说检查列表的大小是常数时间，但我不明白为什么。
我的理解是列表不存储在连续的内存块中（如数组），这意味着如果不先遍历每个列表，就无法获取列表的大小（最后一个元素索引 + 1）元素.
想法？
在不保留手头位置的情况下查找列表长度的唯一方法是遍历列表。它们不存储在块中，因此需要迭代直到到达最后一个元素。因此时间复杂度为 O(n)。当然，如果您存储一个保存长度的变量并在每次添加元素时递增它（并在删除元素时递减），则不需要遍历它，这将使它保持不变，因为您只需要第一个元素，或从存储长度的任何地方检索数据。也许可以使用根元素来保存长度，因此无需循环遍历它来获取长度。简而言之，你是对的。人们可能会说常量的原因是它是否预先存储。
I've seen many answers online saying that checking the size of a list is constant time.
这个谬误可能源于 Python 语言的一个根本缺陷：数组在 Python 中被称为 lists。随着 Python 越来越受欢迎，list 这个词变得模棱两可。
计算链表的长度是一个 O(n) 操作，除非长度已单独存储并妥善维护。
如果大小与数组一起存储，则检索数组的大小是在常数时间内执行的，如 Python 中的情况，因此 a=[1,2,3]; len(a) 确实非常快。
如果必须扫描数组以查找终止值（例如空指针或空字节），则计算数组的长度可能是一个 O(n) 操作。因此，C 中的 strlen() 计算 C 字符串中的字节数（char 的空终止数组）以线性时间运行。