求解面试题目中的复杂度

面试出了一道题，做出来了但是复杂度没有想明白，求解 ~~题目要求string1的任意排序是否出现在string2，返回TRUE or FALSE。下面备注的l1和l2分别是s1和s2的长度，大概推出单独一步的复杂度，但是全部下来就算不明白了。

1. from collections import Counter
   
2. 
   
3. def func(s1, s2):
   
4.   if len(s2) < len(s1):
   
5.   return False
   
6. 
   
7.   c1 = Counter(s1) # O(L1)
   
8.   n = len(s1)
   
9.   for i in range( len(s2)-n+1 ): # O(L2-L1)
   
10.     substring = s2[i:i+n]
    
11.     c2 = Counter(substring)  # O(L1)
    
12.     if c1 == c2:   # O(1), 因为最多26*2个大小写字母
    
13.       return True
    
14.   return False

复制代码

希望面试官给过~~

顺便求点米，感谢！

O(l1*l2)

我怎么觉得是O((l2-l1) * l1 * l1)
因为line 10 你做了string slice python里这个是O(n) -> O(l1)
然后line 11 counter也是O(l1)

清蓬村民 发表于 2021-11-7 18:57
O(l1*l2)

请问可以展开说说吗？为什么不是O( (L2-L1) * L1 )呢？

Maxtk7xox 发表于 2021-11-7 19:51
我怎么觉得是O((l2-l1) * l1 * l1)
因为line 10 你做了string slice python里这个是O(n) -> O(l1)
然后li ...

slicing是O(1)吧

Decau 发表于 2021-11-07 20:30:28
请问可以展开说说吗？为什么不是O( (L2-L1) * L1 )呢？

数量级是一样的

Maxtk7xox 发表于 2021-11-07 19:51:24
我怎么觉得是O((l2-l1) * l1 * l1)
因为line 10 你做了string slice python里这个是O(n) -> O(l1)
然后line 11 counter也是O(

10和11又不是嵌套的循环…..

Shubin_ren 发表于 2021-11-7 21:00
数量级是一样的

是考虑了L1在[1,L2)的范围，当作平均L2/2了？

Decau 发表于 2021-11-07 21:04:35
是考虑了L1在[1,L2)的范围，当作平均L2/2了？

复杂度不是这样算的…..

O(l1*l2)复杂度是算渐近的，能问一下是哪家公司么，最优的应该是sliding window吧