这个算法的复杂度是多少，是否有改进的可能？

Question

这道题的算法是：写一个函数，输入两个数组，每个数组包含一个A-Z的列表；你的程序应该 return True 如果第二个数组是第一个数组的子集，否则为 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 添加一个额外的 space。所以新算法具有 O(n) space 复杂度，而原始算法 - O(1).

Answer 2

我不会给你写代码，因为这是一道作业题。我给你描述一个算法，你自己去实现吧。

以你的arr1和arr2为例，先对arr1进行预处理，存储A-Z出现的次数。所以对于你的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，你的程序应该returnfalse，否则 true.

Answer 3

您的代码的时间复杂度为 O(M*N) - 因为您正在搜索 arr1 中是否存在每个匹配项目arr2.

中的项目

更好的方法是使用 Count 数组并在线性时间和常数 Space 中求解。

此代码的复杂性：

时间复杂度：O(M + N)
Space 复杂度：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

这个算法的复杂度是多少，是否有改进的可能？

What is the complexity of this algorithm and is there a possibility to improve it?

python

algorithm

time-complexity

python-3.x