Задача на линейный поиск в двухмерном массиве

Информатика
1

Условие: Задана матрица K, содержащая n строк и m столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.

Найдите количество седловых точек заданной матрицы.

Входные данные: Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 750). Далее следуют n строк по m чисел в каждой. j-ое число i-ой строки равно k_\text{ij}. Все k_\text{ij} по модулю не превосходят 1000.

Мои идеи:

n_and_m=list(map(int,input().split()))
n=n_and_m[0]
m=n_and_m[1]
matrix=[]
c=0
for i in range(n):
    row=list(map(int,input().split()))
    matrix.append(row)
def row_min(x):
    for i in row:
        if x>i:
            return False
    return True
def col_max(x,i):
    for k in range(n):
        if matrix[k][i]>x:
                return False
    return True
for row in matrix:
    for i in range(m):
        if row_min(row[i]) and col_max(row[i],i):
            c+=1
print(c)

Оно прошло 29 из 36 тестов на сайте, а к остальным один и тот же комментарий: “Превышено максимальное время работы”. Видимо это значит что мое решение не очень эффективно. Можете посмотреть и указать, почему, и как можно лучше(ну и в целом если что-то криво написано, то поправить)? С big O notation знаком, но пока не почувствовал как самому определять, что эффективно, а что нет.

(наверное можно было спросить у ChatGPT, но возможно разделу информатики на этом форуме не хватает тем)

1 лайк
2

Сложность программы O(n * m * (n + m)).

В худшем случае количество операций 750 * 750 * 1500 = 843750000. C++ в секунду может выполнять 10^8, 10^9 операций, но питон намного медленнее поэтому тут происходит time limit.

def row_min(x):
    for i in row:
        if x>i:
            return False
    return True
def col_max(x,i):
    for k in range(n):
        if matrix[k][i]>x:
                return False
    return True

Давай посмотрим сколько раз работает первая функция если у нас n = 3, m = 3.

Для (0, 1), (0, 2), (0, 3) мы ее запускаем 3 раза просто так по идее, пытаясь понять есть ли какой то элемент меньше нашего элемента.

То есть грубо говоря для каждой строки мы запустим m раз функцию row_min.

Решение:

Спойлер

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

4 лайка