查找数组长度的时间复杂度 [英] Time Complexity of finding the length of an array

问题描述

对于 len（）函数的时间复杂度，我有些困惑。

I am a little confused on what the time complexity of a len() function would be.

我在许多不同的文章中读到，在python中找到数组的长度是 O（1）与 len（）函数以及其他语言的类似函数。

I have read in many different posts that finding the length of an array in python is O(1) with the len() function and similar for other languages.

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

How is this possible? Do you not have to iterate through the whole array to count how many indices its taking up?

推荐答案

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

Do you not have to iterate through the whole array to count how many indices its taking up?

不，您不会。

您通常可以随时进行交易

You can generally always trade space for time when constructing algorithms.

例如，在创建集合时，分配一个单独的变量来保存大小。然后将其添加到集合中时增加，而将其删除时则减少。

For example, when creating a collection, allocate a separate variable holding the size. Then increment that when adding an item to the collection and decrement it when removing something.

然后，voilà，集合的大小可以在<$ c $中获得仅通过访问该变量即可达到c> O（1）的时间。

Then, voilà, the size of the collection can then be obtained in O(1) time just by accessing that variable.

这似乎是Python实际执行的，根据此页面，其中指出（检查Python源代码表明这是操作当请求大量对象的大小时）：

And this appears to be what Python actually does, as per this page, which states (checking of the Python source code shows that this is the action when requesting the size of a great many objects):

Py_SIZE（o） -此宏用于访问Python对象的 ob_size 成员。扩展为（（（（PyVarObject *）（o））-> ob_size）。

这篇关于查找数组长度的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！