Уменьшение сложности времени выполнения !!! Сокращение вложенных циклов в Python

Question

Я работаю над программой python, которая дает / принимает стандартный ввод / вывод. В первой строке указано количество тестовых случаев T . Вторая строка дает размер данных N . Третья и четвертая строка дают целых чисел, разделенных пробелами соответственно длины N . Программа упорядочивает Set A и B , чтобы Set A имел максимальное количество элементов, превышающее их равно индексированных элементов в Set B . Ниже мой код:

 def main():
   T=int(input())
   for ii in range(T):
        N=int(input())
        revo=list(map(int, input().split()))
        star=list(map(int, input().split()))
        win=0
        for i in range(N):
            a=1
            for j in range(revo[i]):
                b=revo[i]-a
                if b in star:
                    win=win+1
                    t=star.remove(b)
                    break
                a=a+1
        print(win)
main()

Входы :

1
10
3 6 7 5 3 5 6 2 9 1
2 7 0 9 3 6 0 6 2 6

Выход 7 , потому что при оптимальном расположении набор A имеет 7 элементов, которые больше, чем в наборе B. Но когда мы вводим большие наборы данных, на получение результата уходит много времени. Есть ли какие-нибудь лучшие функции, которые я могу использовать для сокращения времени выполнения?

Answer 1

Ваше решение - O(k*n^2), что действительно много.

 def main():
   T=int(input())
   for ii in range(T): # ignoring number of inputs in time complexity
        N=int(input())
        revo=list(map(int, input().split())) # O(n), doesn't matter
        star=list(map(int, input().split())) # O(n), doesn't matter
        win=0
        for i in range(N): # n
            a=1
            for j in range(revo[i]): # n*k, k depends on 
                                     # how big is each number, hard to tell
                b=revo[i]-a
                if b in star: # k*n^2
                    win=win+1
                    t=star.remove(b) # normally this would multiply by n, but
                                     # remove can be called at most n times 
                    break
                a=a+1
        print(win)
main()

Вы можете одеться до O(nlogn), если сначала отсортируете оба списка. Вот мое решение:

def solve(list1, list2):
    list1 = sorted(list1) # n*logn
    list2 = sorted(list2) # 2*n*logn
    pos_in_list1, pos_in_list2 = 0, 0
    while pos_in_list1 < len(list1): # 2*n*logn + n
        if list1[pos_in_list1] > list2[pos_in_list2]:
            pos_in_list1 += 1
            pos_in_list2 += 1
        else:
            pos_in_list1 += 1
    return pos_in_list2


print(solve([3, 6, 7, 5, 3, 5, 6, 2, 9, 1], [2, 7, 0, 9, 3, 6, 0, 6, 2, 6]))
# 7


def main():
    _ = input()  # we don't need n
    list1 = [int(i) for i in input().split()] # O(n), doesn't matter
    list2 = [int(i) for i in input().split()] # O(n), doesn't matter
    print(solve(list1, list2))

O(2*n*logn + n) = O(nlogn)