Разделяй и властвуй
Давайте узнаем, какие алгоритмы придуманы людьми и как они вам помогут в жизни.
Представьте, что вы Google и какой-то человек просит вас найти значение слова "Алгоритм".
Если бы вы были машиной, которая не имеет глаз и осуществляет поиск, основываясь на математике, то как бы вы нашли нужный человеку сайт?
1 вариант: Вы последовательно переберёте миллиард сайтов и покажете человеку те, на которых присутствует слово "Алгоритм". Такой линейный поиск прост, но пройдёт много секунд, прежде чем вы найдёте лучший сайт.
2 вариант: Вы будете "разделять и властвовать". Вы заранее упорядочили 1.000.000.000 сайтов по алфавиту от "Абажур" до "Аятолла" и теперь, при запросе человеком слова "Алгоритм", вы выберете средний, т.е. 500.000.000-й сайт в списке, поймёте, что данный сайт содержит слово "Амулет", выберите 250.000.000-й сайт, он содержит слово "Азарт", выберите 375.000.000-й сайт и о чудо! Всего за 3 хода вместо 375.000.000 ходов мы нашли заветную группу сайтов со словом "Алгоритм". Такой бинарный поиск прост и пройдут какие-то миллисекунды, прежде чем вы найдёте лучший сайт.
В последующих статьях вы научитесь использовать бинарный и более мощные алгоритмы для решения своих задач.
Назад: Миром правят алгоритмыДалее: Готовимся к бинарному поиску
Источник: РВЭБ2018-01-08