Python内置函数zfill的时间复杂度（Big O）是多少？

嘿，这个问题问得很到位！咱们来一步步理清楚zfill()的时间复杂度：

首先，先回忆下zfill()的功能：它会在字符串左侧填充0，直到整个字符串的长度达到你指定的参数值。比如"hello".zfill(8)会返回"000hello"。

时间复杂度结论 #

zfill()的时间复杂度是O(n)，这里的n指的是你指定的目标字符串长度。

为什么是O(n)？ #

Python里的字符串是不可变对象，所以调用zfill()时，本质是创建一个全新的字符串：

• 如果原字符串长度小于目标长度，需要先生成(目标长度 - 原字符串长度)个0，再把原字符串拼接在后面。这个过程需要遍历并构造总长度为n的新字符串，每个字符都要被处理一次，时间和n成正比。
• 如果原字符串长度已经大于等于目标长度，zfill()会直接返回原字符串的副本（或者原字符串本身，取决于具体实现，但无论哪种，时间复杂度都是O(m)，其中m是原字符串长度，而m≤n，所以最坏情况还是O(n)）。

简单来说，不管哪种情况，zfill()的时间开销都和最终生成的字符串长度线性相关，所以是线性时间复杂度O(n)。

内容的提问来源于stack exchange，提问作者Zejak