python - Python 的 len() 内置 O(1) 时间复杂度背后的 secret 是什么？

Closed. This question is not reproducible or was caused by typos。它当前不接受答案。












想改善这个问题吗？更新问题，以便将其作为on-topic用于堆栈溢出。

2年前关闭。



Improve this question




由于Python是用C实现的，所以我很困惑开发人员如何使Python内置的len函数在恒定时间O(1)上以任何顺序运行，而C的字符串函数strlen在线性时间O(n)上运行。

Python内置的len函数的时间复杂度背后的 secret 是什么？如果我们要用C编写程序，那么如果我们想对涉及序列长度的快速C程序进行复制，最好的做法是将Python的代码复制为len？

最佳答案

我猜您错过了一个概念，即数据结构如何在恒定时间内返回其大小，即 O(1)。

粗略地，想想这样的程序:

void init(){
     // code to initialize (or allocate memory) the container
     size = 0;
}
void add(Something something){
     container.add(something);
     size++;
}
void remove(Something something){
   //Code to search 'something'
   if(found) {
    container.remove(something);
    size--;
   }
}
int len(){
    return size;
}

现在，无论何时您调用 len() 方法，它都准备好返回整数值 而无需遍历 container 。

为什么 strlen 或任何与 C 相关的数据结构不能那样工作是因为拥有像 size 这样的计数器的空间开销。但这并不意味着你不能定义一个。
暗示:
使用 struct 并将大小保持在那里。

关于python - Python 的 len() 内置 O(1) 时间复杂度背后的 secret 是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52134512/