python - Python函数复杂度

Question

我被问及此功能的最佳和最坏情况：

def is_palindromic(the_list):

    result = True 
    the_stack=Stack()
    for item in the_list:
        the_stack.push(item)
    for item in the_list:
        item_stack=the_stack.pop()
        if item != item_stack:
            result = False
    return result

此函数使用堆栈确定列表是否与其反向相同。我认为每种情况的时间复杂度都是相同的，但是当我测试时，如果列表确实与其反向相同，则运行时间会更长。谁能解释为什么？我有点困惑。

标签： pythonalgorithmdata-structurestime-complexity

Answer 1

两种情况都是O(n)。你总是加载堆栈，这应该是一个O(n)操作。在最好的情况下，第一个字符与最后一个字符不匹配，因此搜索应该立即终止。在最坏的情况下，所有字符都匹配，因此程序会再次n弹出和比较。O(2n)还在O(n)。

请记住，即使在确定单词不是回文之后，当前代码也会进行相同的弹出和比较。该行result = False应该return False或至少后跟一个break语句。使最坏情况运行速度变慢的原因可能是非回文单词会有很多不匹配，导致该if块重复执行result以False一遍又一遍地设置。这不会改变复杂性，因为它是一个恒定时间操作。