擅长:python、mysql、java
<p>算法的复杂度为<code>O(n*k)</code>,其中<code>n</code>和<code>k</code>是数组的长度。在另一个循环中有一个循环,在列表中搜索需要<code>O(n)</code></p>
<pre><code>for i in range(len(arr2)):
if(arr2[i] not in arr1) # inner loop because of `in` with `O(n)` complexity
</code></pre>
<p>您可以优化算法:</p>
<pre><code>s = set()
for el in arr1:
s.add(el)
for el in arr2:
if el not in s:
return False
return True
</code></pre>
<p>在这种情况下,时间复杂度为<code>O(n+k)</code>,其中<code>n</code>和<code>k</code>是数组的长度。在<code>set</code>中搜索(并且<code>dict</code>具有<code>O(1)</code>时间复杂性)</p>
<p>但是在这种情况下,您需要为<code>set</code>添加一个额外的空间。因此,新算法具有<code>O(n)</code>空间复杂度,而原算法具有<code>O(1)</code>空间复杂度</p>