Python的len()内置时间复杂度O(1)背后的秘密是什么

Question

由于Python是用C实现的,我很困惑开发人员如何设法使Python内置len函数在常量时间O(1)上的任何序列上运行,而C的字符串函数strlen以线性时间O(n)运行.

Python内置len函数的时间复杂性背后的秘密是什么？如果我们用C编写程序,len如果我们想要一个快速的C程序涉及序列长度,那么复制Python代码是最佳做法吗？

Answer 1

我猜你错过了一个概念,即数据结构如何在恒定时间内返回其大小,即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并保持大小.