@wqrfgdgtttte

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

Мне нужно определить время выполнения алгоритма поиска элемента в квадратной матрице по BigO во всех случаях
Мне кажется. что и лучшим, и средним. и худшим будет n^2. Если б массив был отсортирован, то может можно было еще делить массив пополам пока не найдется число, а так идей больше нет. Действительно ли нет больше вариантов?
  • Вопрос задан
  • 77 просмотров
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Если нет никакой сортировки, то худший и средний O(n^2). Лучший - O(1).
Если упорядочена каждая строка, то можно за O(n log n). Опять в худшем и среднем. Лучший - O(1) везде.
Если упорядочены каждая строка и столбец, то можно за O(n) найти в худшем и среднем случае (лучший не меняется). Если упорядочены все числа (не только внутри каждой строки, но как бы в одном длинном одномерном массиве), то можно за O(log n).
Ответ написан
Комментировать
AshBlade
@AshBlade
Просто хочу быть счастливым
Самый эффективный алгоритм поиска - бинарный. Это O(log N) для отсортированного массива.
Но надо еще понять, как расположены элементы в квадратной матрице.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы