Какое время выполнения у алгоритма поиска элемента в матрице?

Question

[wqrfgdgtttte]

Мне нужно определить время выполнения алгоритма поиска элемента в квадратной матрице по BigO во всех случаях
Мне кажется. что и лучшим, и средним. и худшим будет n^2. Если б массив был отсортирован, то может можно было еще делить массив пополам пока не найдется число, а так идей больше нет. Действительно ли нет больше вариантов?

Answer 1

[Wataru]

Если нет никакой сортировки, то худший и средний O(n^2). Лучший - O(1).
Если упорядочена каждая строка, то можно за O(n log n). Опять в худшем и среднем. Лучший - O(1) везде.
Если упорядочены каждая строка и столбец, то можно за O(n) найти в худшем и среднем случае (лучший не меняется). Если упорядочены все числа (не только внутри каждой строки, но как бы в одном длинном одномерном массиве), то можно за O(log n).

Answer 2

[Сергей Соловьев]

Самый эффективный алгоритм поиска - бинарный. Это O(log N) для отсортированного массива.
Но надо еще понять, как расположены элементы в квадратной матрице.

Если без сортировки, то надо перебрать все элементы - это O(N^2).

Другой случай - она (матрица) отсортирована. Тут надо сделать уточнение, что отсортирована может быть только по строкам, либо столбцам, т.е. градиентного (если так можно выразиться) представления нет. Для асимптотики разницы никакой между построчной и постолбцовой сортировки (с точки зрения кэша - лучше построчное).
Тогда сложность поиска будет O(N * logN), т.к. тебе надо будет пройти по каждой строке (N) и выполнить для нее бинарный поиск (log N).