Сравнение эффективности двух алгоритмов: Найти количество отрицательных целых чисел в отсортированной по строке / столбцу матрице

Question

Вот ссылка на полный вопрос: https://youtu.be/5dJSZLmDsxk Вопрос: Создать функцию, которая возвращает число отрицательных целых чисел в двумерном массиве, так что целые числа каждой строки в этом массиве увеличиваются в размере от индекса 0 до n, в то время как целые числа каждого столбца делают то же самое сверху вниз , Э.Г.

{{-5, -4, -3, -2},
 {-4, -3, -2, -1},
 {-3, -2, -1,  0},
 {-2, -1,  0,  1}}

В видео CS Dojo представляет следующее решение:

def func(M, n, m):
    count = 0
    i = 0
    j = m - 1
    while j >= 0 and i < n:
        if M[i][j] < 0:
            count += j + 1
            i += 1
        else:
            j -= 1
    return count

Мои вопросы: почему / следующий код не так эффективен? (Единственное отличие состоит в том, что последний начинается слева и увеличивается count несколько раз <- Но будут ли эти две вещи иметь какое-то значение? </p>

int rows = 3;
int cols = 4;

int count_neg(const int arrays[rows][cols]) {
    int count = 0;
    int pos = cols;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j <= pos; j++) {
            if (arrays[i][j] < 0)
                count++;
            else {
                pos = j;
                break;
            }
        }
        if (pos == 0)
            break; /*offers miniscule efficiency improvement?*/
    }
    return count;
}

Пожалуйста, предположите, что они оба были написаны на одном языке.

Answer 1

Разница в том, что вторая версия сканирует все матрицы отрицательных чисел и занимает O (n * m) время (вся матрица может быть отрицательной), в то время как первая отслеживает границу между отрицательные и неотрицательные элементы, и занимает O (n + m) время.

Чтобы увидеть, как работает первая, рассмотрим: каждая итерация будет либо увеличивать i, либо уменьшать j. i может быть увеличено только n-1 раз, а j может быть уменьшено только m-1 раз.