как уменьшить сложность времени? - PullRequest
Новая
       13

как уменьшить сложность времени?

1 голос
/ 30 апреля 2020

Ниже приводится вопрос: Из матрицы размера nxm мы должны выбрать один элемент из каждой строки, чтобы создать новый массив A размера N. мы найдем sh, чтобы найти минимально возможный значение абсолютной разности между любыми двумя соседними элементами в массиве A. (Примечание: элемент, выбранный из строки 1, станет A [1], элемент, выбранный из строки 2, станет A [2] и т. д.)

Пример ip (для матрицы 2 X 2): 

8   4
6   8

Пример операции: 

0 #(8-8)

Я пробовал следующий код, но он отнимает много времени (5 se c), а ограничение по времени составляет 1 se c. Может ли кто-нибудь помочь в улучшении сложности для кода ... 

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
minimum=abs(l[0][0]-l[1][0])
for i in range(n):
if i+1<n:
    for j in range(m):
        for k in range(m):
            diff=abs(l[i][j]-l[i+1][k])
            if diff==0:
                minimum=diff
                break
            elif diff<minimum:
                minimum=diff
            else:
                continue
print(minimum)

Ответы [ 2 ]

0 голосов
/ 01 мая 2020

Идея

Рассмотрим следующую матрицу: 

8 4 3
6 8 1

Возьмем строку № 1 и строку № 2 и создадим вектор. Так как мы хотим также знать, какой элемент принадлежит какой строке, упакуйте эти элементы с их номером строки. 

two_rows = [(8,1), (4,1), (3,1) (6,2), (8,2), (1,2)]

Это означает, что у нас есть 8, 4, 3 из строки № 1 и 6, 8, 1 из ряда № 2. Теперь отсортируйте этот список (по первому значению кортежей) 

sorted_two_rows = [(1,2), (3,1), (4,1), (6,2), (8,1), (8,2)]

Далее, просмотрите этот список. Учитывайте только соседние кортежи из разных рядов

  • (1,2) и (3,1)
  • (4,1) и (6,2)
  • (6,2) и (8,1)
  • (8,1) и (8,2)

Все остальное просто, просто вычислите абсолютные различия и запишите минимум.

Если вы повторите это для всех соседних строк. Вы должны найти общую минимальную разницу. Это займет O(nm log m).

0 голосов
/ 30 апреля 2020

Оптимизированная реализация: 

diffs = [0] * m
for row, next_row in zip(l, l[1:]):
    diffs = [min(max(diff, abs(value - prev_value)) 
                     for diff, prev_value in zip(diffs, row)) 
             for value in next_row]
return min(diffs)

Должно быть в ~ 10 раз быстрее с numpy массивами.

Ошибка, о которой я упоминал в комментариях: он искал минимум всех минимальных разностей. Тем не менее, они не всегда выстраиваются в очередь. Например: 

[[8, 0, 0],
 [10, 8, 6],
 [6, 12, 0]]

в исходной реализации возвращаемое значение равно 0, что неверно.

...