相关疑难解决方法(0)

我看到很多关于建的方法Python的的运行时间复杂度的问题,有很多答案了很多的方法(例如https://wiki.python.org/moin/TimeComplexity,HTTPS:/ /www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt,LEN()的开销功能,等)

我没有看到任何枚举的内容.我知道它至少返回一个新数组(索引),但生成它需要多长时间,而另一个数组只是原始数组？

换句话说,我假设它是O(n)用于创建新数组(迭代)和O(1)用于重用原始数组...总共O(n)(我认为).副本的另一个O(n)是否为O(n ^ 2),或其他什么......？

到现在为止，当我将该len函数与各种容器类型（list假设现在的类型）一起使用时，我假设每个容器类型都有一个字段成员，用于存储该特定对象的长度.. 来自 Java，这做了很多感觉。但是当我想到它时，我不认为这是真的，这让我感到困惑。

每当我len在一个实现的对象上使用该函数时__length__，它是通过迭代对象的元素来计算长度，还是立即以某种方式返回长度？

这个问题实际上来自使用dict内置类型。我向字典中添加了一些元素（很多），最终我需要获取字典中元素的数量，所以因为我不确定len函数的时间复杂度是多少，我决定将这些元素计算为我插入它们...但我不确定这是我问题的正确解决方案。

这是我的问题的示例代码：

d = {}
count = 0
for i in range(10 ** 6):
    d[i] = True
    count += 1

VS

d = {i: True for i in range(10 ** 6)}
count = len(d)

第二个解决方案对我来说看起来更好（和更短）......而且我知道理论上无论len函数是否即时，时间复杂度都是相同的，在第二个解决方案中，我担心它迭代两次到 10 ** 6 （第一个用于字典理解，其次用于长度计算）。

请赐教。

class Song:
    def __init__(self, name):
        self.name = name
        self.next = None

    def next_song(self, song):
        self.next = song 

    def is_repeating_playlist(self):
        """
        :returns: (bool) True if the playlist is repeating, False if not.
        """
        return None

first = Song("Hello")
second = Song("Eye of the tiger")

first.next_song(second);
second.next_song(first);

在 上调用 Python 的内置len()函数的时间复杂度是collections.deque多少？我希望它是 O(1)，但我还没有找到对这个事实的任何确认。

这是一个python问题。答案应该是 O(n) 时间复杂度并且不使用额外的内存。作为输入，我得到一个应该归类为回文或不归类的字符串（回文是一个单词或短语，可以从左到右和从右到左阅读相同的单词或短语，fe“级别”）。在输入中可以有标点符号和单词之间的间隙。例如“我。做了，，，我是吗？？？？” 主要目标是确定输入是否为回文。

当我试图解决这个问题时，我遇到了几个挑战。当我尝试删除非字母数字时

for element in string:
    if ord(element) not in range(97, 122):
        string.remove(element)
    if ord(element) == 32:
        string.remove(element)

我使用 O(n^2) 复杂度，因为对于字符串中的每个元素，我都使用 remove 函数，它本身具有 O(n) 复杂度，其中 n 是列表的长度。我需要帮助通过消除 O(n) 复杂度的非字母字符来优化部件

此外，当我们去掉空格作为标点符号时，我知道如何检查一个单词是否是回文，但我的方法使用了额外的内存。

类似的问题已经在这里询问成本len()函数.然而,这个问题着眼于len它的成本.假设,我有一个重复多次的代码len(List),每次都是O(1),读取变量也是O(1)加分配它也是O(1).

作为旁注,我发现它n_files = len(Files)比len(Files)我的代码中的重复更具可读性.所以,这对我来说已经是一种激励.你也可以反对我,代码中的某个地方Files可以修改,所以n_files不再正确,但事实并非如此.

我的问题是:访问后
的一些调用 会更快吗？len(Files)n_files

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

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

例子：

a = {a:'1', b:'2'}
len(a)

的时间复杂度是len(a)多少？

根据这个答案,呼叫len(s)的复杂度为O(1).那么为什么在一个下载的27kb文件上调用它比在一个1kb的文件上慢得多呢？

27KB

>>> timeit.timeit('x = len(r.text)', 'from requests import get; r = get("https://cdn.discordapp.com/attachments/280190011918254081/293010649754370048/Journal.170203183244.01.log")', number = 20)
5.78126864130499

1KB

>>> timeit.timeit('x = len(r.text)', 'from requests import get; r = get("https://cdn.discordapp.com/attachments/280190011918254081/293016636288663562/Journal.170109120508.01.log")', number = 20)
0.00036539355403419904

问题是,这个例子在我的开发机器上运行,这是一台普通的工作电脑.运行代码的机器是RaspberryPi,它的速度要慢几个数量级.