查找数组长度的时间复杂度

我对时间复杂度有点困惑len()函数将是。

我读过很多不同的文章，在 python 中查找数组的长度是O(1)与len()函数和其他语言类似。

这怎么可能？您是否不必遍历整个数组来计算它占用了多少个索引？

您是否不必遍历整个数组来计算它占用了多少个索引？

你不可以。

在构建算法时，您通常总是可以用空间换取时间。

例如，创建集合时，分配一个单独的变量来保存大小。然后，在向集合中添加项目时增加该值，并在删除某些内容时减少该值。

然后，瞧，集合的大小可以通过以下方式获得：O(1)只需访问该变量即可。

这似乎就是 Python 实际所做的，根据这一页 https://docs.python.org/3/c-api/structures.html，其中指出（检查Python源代码表明这是请求大量对象的大小时的操作）：

Py_SIZE(o)- 该宏用于访问ob_sizePython 对象的成员。它扩展到(((PyVarObject*)(o))->ob_size).

如果比较这两种方法（迭代与长度变量），每种方法的属性如下表所示：

在这种情况下，额外的成本是最小的，但获得长度所节省的时间可能是相当可观的，所以这可能是值得的。

那不是always这种情况是因为，在某些（罕见）情况下，增加的空间成本可能超过减少的时间（或者可能需要比可用空间更多的空间）。

举例来说，这就是我正在谈论的内容。忽略在 Python 中完全没有必要的事实，这是一种神话般的类似 Python 的语言，它具有O(n)查找列表长度的成本：

import random

class FastQueue:
    """ FastQueue: demonstration of length variable usage.
    """
    def __init__(self):
        """ Init: Empty list and set length zero.
        """
        self._content = []
        self._length = 0

    def push(self, item):
        """ Push: Add to end, increase length.
        """
        self._content.append(item)
        self._length += 1

    def pull(self):
        """ Pull: Remove from front, decrease length, taking
                  care to handle empty queue.
        """
        item = None
        if self._length > 0:
            item = self._content[0]
            self._content = self._content[1:]
            self._length -= 1
        return item

    def length(self):
        """ Length: Just return stored length. Obviously this
                    has no advantage in Python since that's
                    how it already does length. This is just
                    an illustration of my answer.
        """
        return self._length

    def slow_length(self):
        """ Length: A slower version for comparison.
        """
        list_len = 0
        for _ in self._content:
            list_len += 1
        return list_len

""" Test harness to ensure I haven't released buggy code :-)
"""

queue = FastQueue()

for _ in range(10):
    val = random.randint(1, 50)
    queue.push(val)
    print(f'push {val}, length = {queue.length()}')

for _ in range(11):
    print(f'pull {queue.pull()}, length = {queue.length()}')