时间戳

首页 > 解决方案 > 如果您有固定的列表大小，此代码是否为 O(1)

python-3.x - 如果您有固定的列表大小，此代码是否为 O(1)

问题描述

例如，您正在遍历列表中的字母，但您必须检查标点符号。下面的代码仍然是 O(n)，n 是一行中的最大字符吗？我认为这是因为标点符号列表是固定大小的，所以 if 语句仍然是 O(1) 对吗？

punctuation = [',', '.', '?', '!', ':', ';', '"', ' ', '\t', '\n']   
for letters in line:
        if letters not in punctuation:
            word += letters

标签： python-3.xtime-complexitybig-ocomputer-science

解决方案

是的，你是对的，因为标点符号列表的大小是固定的（并且不依赖于 N），所以你的代码的整体时间复杂度应该是 O(N)。正如其他评论员所指出的那样，O(N*M) 可能更精确，其中 N 是您正在阅读的字符总数，而 M 是标点符号字符的数量。

如果要在那里进行优化，可以将标点符号存储在 a 中set，其中in以恒定时间运行：

punctuation = {',', '.', '?', '!', ':', ';', '"', ' ', '\t', '\n'} 
for letter in line:
    if letter not in punctuation:
        word += letter

推荐阅读