Матрицы Теплица

Добро пожаловать обратно с еще одной головоломкой, чтобы решить! На этот раз у нас есть задача о матрицах: в частности, теплицевых матрицах! Мы сейчас увидим, что они из себя представляют, как только погрузимся прямо в проблему, которую на этот раз задал Google. Готовы тогда? Выясним проблему!

В линейной алгебре матрица Теплица — это матрица, в которой элементы на любой заданной диагонали от верхнего левого угла до нижнего правого одинаковы.

Вот пример:

1 2 3 4 8
5 1 2 3 4
4 5 1 2 3
7 4 5 1 2

Напишите программу, определяющую, является ли данный вход теплицевой матрицей.

Тогда проблема понятна: нам нужно проверить, является ли данная матрица матрицей Теплица или нет!

Давайте подумаем об этом тогда.

С технической точки зрения

Давайте дадим правильное определение такого рода матрице: матрица Теплица — это матрица, в которой каждая нисходящая диагональ слева направо постоянна. Например, это может быть матрица Теплица:

[
  [1,3,2,5],
  [6,1,3,2],
  [0,6,1,3],
  [9,0,6,1]
]

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

[
  [1,3,2,5],
  [6,1,3,2],
  [0,6,1,3],
]

Это приводит нас к важному факту. Математическое определение такого типа матрицы будет примерно таким:

Это означает, что элементы в позиции [m,0] и элемент в позиции [0,n] могут быть фактически «отброшены», так как у них больше нет элементов для сравнения. В нашем примере числа 0 и числа 5 не имеют дополнительных строк и столбцов с другими 0 и 5, поэтому они не имеют отношения к свойству матрицы.

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

И это будет наша хитрость для решения проблемы.

Решение

Решение будет написано на Python. Вот реализация:

Давайте посмотрим поближе. Во-первых, мы определяем функцию ToeplitzCheck, которая принимает нашу матрицу в качестве аргумента. Мы инициализируем две переменные:

  • crntRow,, который будет содержать индекс строки, по которой мы зацикливаемся;
  • maxRow,, которая представляет собой простую переменную, содержащую длину матрицы (можно пропустить, просто используя вместо нее len(matrix).

После этого перебираем ряды, до предпоследнего: после последнего сравнивать будет не с чем! Теперь мы просто cсравним первые n-1 элементы из строки, в которой мы находимся, с последними n-1 элементами следующей строки: если они отличаются, мы возвращаем False и это не тёплицева матрица. Если мы не возвращаемся, мы увеличиваем cntRow на единицу, чтобы перейти к следующей строке. Наконец, если весь цикл не вернулся, мы возвращаем True, что означает, что матрица на самом деле является матрицей Теплица.

Временная сложность

Как всегда, давайте обсудим временную сложность приведенного выше алгоритма. На первый взгляд может показаться, что это O(n)-алгоритм, так как самая трудоемкая его часть — это цикл while, полностью зависящий от длины матрицы. Хотя на самом деле это может быть не так.

Сравнение массивов — нетривиальная операция. Каким бы хорошим ни был Python, чтобы скрыть сложность кода, массив равен другому тогда и только тогда, когда все его элементы одинаковы. . По этой причине сравнение двух массивов должно быть равным для сравнения всех их элементов. Тип массива Python должен иметь реализованный метод, который сравнивает все элементы. Но если бы мы писали алгоритм на другом языке, скорее всего, мы реализовали бы собственную функцию сравнения. Возьмем, к примеру, Go: сравнение массивов не является основным методом типа массива, поэтому мы должны создать такую ​​функцию:

Глядя на эту функцию, становится ясно, что сравнение двух массивов — операция, требующая O(n) времени, где n — длина сравниваемых массивов. Добавляя это к нашему решению выше, мы получаем временную сложность O(m*n), где m — количество массивов (строк), а n — количество элементов в каждой строке (столбцах).

Вот и все! Надеюсь, вам понравилась статья и что она оставила что-то ценное! Если да, поставьте лайк и поделитесь статьей с кем-нибудь, кому это может быть полезно.

Спасибо за чтение, как всегда.

Никола