算法复杂度分析若干实例
记录leetcode每日一题算法复杂度分析过程：
2020.10.14
查找常用字符
题目链接 == >https://leetcode-cn.com/problems/find-common-characters/
class Solution:
def commonChars(self, A: List[str]) -> List[str]:
minfreq = [float("inf")] * 26
for word in A:
freq = [0] * 26
for ch in word:
freq[ord(ch) - ord("a")] += 1
for i in range(26):
minfreq[i] = min(minfreq[i], freq[i])
ans = list()
for i in range(26):
ans.extend([chr(i + ord("a"))] * minfreq[i])
return ans
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-common-characters/solution/cha-zhao-chang-yong-zi-fu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度分析
-
时间复杂度：(O(n(m+|Sigma|))),其中 (n)是数组 (A) 的长度（即字符串的数目），(m)是字符串的平均长度，(Sigma)为字符集，在本题中字符集为所有小写字母，(|Sigma|=26)。
- 遍历所有字符串并计算(freq)的时间复杂度为(O(nm))；
- 使用(freq)更新(minfreq)的时间复杂度为(O(n|Sigma|))；
- 由于最终答案包括的字符合数不会超过最短的字符串长度，因此构造最终答案的时间复杂度为(O(m+|Sigma|))。这一项在渐进意义上小于前两者可以忽略。个人理解本项计算分为两部分，遍历的部分操作时间复杂度为(O(|Sigma|*1))，扩充答案列表的操作时间复杂度(O(minLength(A的字符)*1) <=O(m*1))。
-
空间复杂度：(O(|Sigma|)),这里只计算存储答案之外的空间我们使用数组(freq)和(minfreq),他们的长度均为(|Sigma|)。