Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
OxomHuK
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241
1

Поиск максимального элемента в двумерном массиве

15.08.2013, 01:01. Просмотров 575. Ответов 3
Метки нет (Все метки)

Здравствуйте! Собственно вопрос - оптимальный алгоритм. Есть ли тут вообще алгоритм который находит быстрее чем перебором за O(mxn)
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.08.2013, 01:01
Ответы с готовыми решениями:

Поиск максимального элемента в массиве методом "разделяй и властвуй"
Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его...

Поиск медианы в двумерном массиве
Объявляется конкурс на лучший алгоритм/функцию для нахождения значения медианы двумерного массива.

Поиск группы разных элементов в двумерном массиве
Есть задача - в двумером массиве размером, например, 100х100 найти координаты квадратов размером,...

Поиск максимального элемента, который меньше заданного
Идея следующая: есть набор значений: 1, 5, 8, 32, 116 на вход поступает одно значение: 10...

Поиск элемента в отсортированном массиве
какое минимальное колличество итераций при поиске элемента в отсортированом массиве по возрастанию...

3
Mysterious Light
Эксперт по математике/физике
4082 / 1995 / 405
Регистрация: 19.07.2009
Сообщений: 3,012
Записей в блоге: 21
15.08.2013, 10:14 2
Без какой-либо доп. информации о массиве — не существует.
Нужно по меншей мере каждый элемент прочитать, иначе алгоритм не будет реагировать на изменение непрочитанных элементов, что не может быть.
Чтение O(1), итого http://www.cyberforum.ru/cgi-bin/latex.cgi?\Omega(nm).
Хотя можно придумать алгоритм, работающий за O(n+m), если имеется возможность обрабатывать строки/столбцы в параллельных потоках.
1
TheAthlete
155 / 155 / 16
Регистрация: 31.08.2010
Сообщений: 540
17.08.2013, 13:10 3
Если представить массив как одномерный и знать, что он отсортирован, то можно спокойно найти максимальный элемент - переый или последний элемент, в зависимости в какую сторону отсортирован.
0
castaway
18.08.2013, 00:30     Поиск максимального элемента в двумерном массиве
  #4

Не по теме:

Цитата Сообщение от TheAthlete Посмотреть сообщение
Если представить массив как одномерный и знать, что он отсортирован, то можно спокойно найти максимальный элемент - переый или последний элемент, в зависимости в какую сторону отсортирован.
Да ты человек - гениальность.

1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.08.2013, 00:30
Привет! Вот еще темы с ответами:

Оптимальный поиск элемента в массиве
Столкнулся с проблемой поиска оптимального алгоритма нахождения индекса нужного мне элемента в...

Двоичный поиск в массиве ВСЕХ вхождений искомого элемента
У Вики есть такой чудесный код: def check(x, m): return x < m def binSearch(lst, x): #...

поиск максимального элемента в двумерном массиве
Написать программу поиска в двумерном массиве максимального и минимального элемента массива. Массив...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru