该算法的复杂度是多少？是否有可能对其进行改进？

Question

这就是这个问题的算法：编写一个函数，以两个数组作为输入，每个数组包含一个a-Z列表；如果 第二个数组是第一个数组的子集，如果不是，则为False

# Python 3 program to find whether an array

def isSubset(arr1, arr2):
    i = 0
    for i in range(len(arr2)):
        if(arr2[i] not in arr1):
            return False
    return True
     
arr1 = ["A", "B", "C", "D", "E", "F"]
arr2 = ["C", "A", "A"]

if(isSubset(arr1, arr2)):
    print("arr2[] is a subset of arr1[] ")
else:
    print("arr2[] is not a subset of arr1[]")

Answer 1

算法的复杂度为O(n*k)，其中n和k是数组的长度。在另一个循环中有一个循环，在列表中搜索需要O(n)

for i in range(len(arr2)):
     if(arr2[i] not in arr1)  # inner loop because of `in` with `O(n)` complexity

您可以优化算法：

s = set()
for el in arr1:
  s.add(el)

for el in arr2:
  if el not in s:
     return False

return True

在这种情况下，时间复杂度为O(n+k)，其中n和k是数组的长度。在set中搜索（并且dict具有O(1)时间复杂性）

但是在这种情况下，您需要为set添加一个额外的空间。因此，新算法具有O(n)空间复杂度，而原算法具有O(1)空间复杂度

Answer 2

代码的时间复杂度是O（M*N）-，因为您正在搜索arr1中是否有一个匹配的项来匹配arr2中的每个项

更好的方法是使用Count数组，并在线性时间和恒定空间中求解它

此代码的复杂性：

• 时间复杂度：O（M+N）
• 空间复杂性：O（26）

arr1 = ["A", "B", "C", "D", "E", "F"]
arr2 = ["C", "A"]

def check(arr1, arr2):
    c1 = [0]*26
    c2 = [0]*26
    a = ord('A')
    for i in arr1:
        if c1[ord(i) - a] == 0:
            c1[ord(i) - a] += 1

    for j in arr2:
        if c2[ord(i) - a] == 0:
            c2[ord(j) - a] += 1

    for i in range(len(c1)):
        if c2[i] > c1[i]:
            return 'Not a Subset'
    return 'Subset'


    
print(check(["A", "B", "C", "D", "E", "F"], ["C", "A"]))
print(check(["B"], ["A", "B"]))
print(check(["A"], ["A", "A"]))
print(check(["A","B"], []))
print(check([], []))

Subset
Not a Subset
Subset
Subset
Subset

Answer 3

我不会为你写代码，因为这是一个家庭作业问题。我将为您描述一个算法，您应该自己实现它

以arr1和arr2为例，首先通过存储A-Z的出现次数来预处理arr1。因此，对于您的arr1，您应该获得：

"A": 1,
"B": 1,
"C": 1,
"D": 1,
"E": 1,
"F": 1,
"G": 0,
...

现在对arr2执行同样的操作，您应该得到：

"A": 2,
"B": 0,
"C": 1,
"D": 0,
...

现在比较这两个列表中A-Z的值，如果arr2的任何对应值大于arr1，则程序应返回false，否则返回true