wignorbo Sep 11 at 09:22

Алгоритмы в повседневной жизни

Easy

6 min

8.9K

From sandbox

+35

Comments 15

Pinned comments

malkovsky Sep 12 at 16:12

Мне кажется, что поиск гораздо лучше аналогия со словарём, отсортированным в лексикографическом порядке. Вот вы хотите найти какое-то слово:

Если вы открываете словарь посередине и смотрите на первую букву пытаясь понять, должно ли ваше слово быть во второй половине или первой, а потом повторяете несколько раз - это бинарный поиск.
Возможно вы филолог и знаете, что слов на букву "а" больше, чем на букву "ы", а может даже знаете априорное распределение для первых, ну или просто осознаёте, что слово на букву "э" будет скорее в конце, чем в начала и смотрите не в середину, а куда-то еще основываясь на априорных знаниях, это интерполяционный поиск.
Возможно это ваш словарь и вы заранее сделали в нём закладки на начало каждой буквы, а может даже и на первые две буквы. Найдя таким образом нужный раздел вы совершили поразрядную сортировку.
Так или иначе в какой-то момент находите нужную страницу и какой-то слово, которое достаточно близко к искомому и уже просто пробегаетесь подряд назад или вперед -- это линейный поиск

Чего многие не осознают, так это то, что на самом деле и практические поисковые алгоритмы гораздо сильнее схожи с человеческим, чем кажется. Например использование интерполяционного поиска на больших массивах сильно уменьшает количество кэш промахов по сравнению с бинарным, а на маленьких массивах линейный поиск может быть заметно лучше других за счет параллельной обработки (на уровне регистров/конвеера).

yukky_997 Sep 11 at 13:16

Я знал что мы в матрице)

apevzner Sep 11 at 14:01

Вы когда-нибудь задумывались, что поиск футболки в шкафу — это O(N)

А разве сложность алгоритма поиска футболки в шкафу это не O(∞)?

chervital Sep 11 at 16:46

А сложность алгоритма поиска парных носков вообще стремится к бесконечности. Особенно если один в шкафу , а другой в стиральной машине.

apevzner Sep 11 at 21:50

А еще они прекрасно демонстрируют принцип квантовой запутанности.

Как только один носок из пары становится левым, другой, мгновенно, становится правым.

wignorbo Sep 11 at 18:27

Если брать вещь и кидать ее обратно в кучу, то да)

Если, например, откладывать в сторону, то O(N)

dyadyaSerezha Sep 12 at 05:07

а вещи не стухли в стиральной машине, которая пропищала уже 4 часа назад

Та ладно. Не 4, а минимум 48 часов надо, а то и всё 72.

совмещать работу, спорт и учебу не только можно,

Маловато будет! Надо добавить жену, тещу, двоих маленьких детей, дела на даче и вторую работу-подработку, чтобы хватало денег на всех, приведенных выше, и ипотеку. Вот тогда поверим.

npocmoKu Sep 13 at 09:48

Можно делегировать общение с детьми жене,общение с женой теще,дела на даче детям,а освободившееся время занять 3-ей работой-подработкой,чтобы денег хватало и на ипотеку и на возражения приведенных выше)))

dyadyaSerezha Sep 13 at 11:22

Земля - крестьянам! Дача - детям!

Если не жалко. Дачу, конечно)

Ivakorn Sep 12 at 08:44

У меня с женой всегда спорт идет за нумерацию первой полки в комоде. Она говорит первая полка сверху - это логично, это всеобщий известный факт. Я говорю первая полка снизу - это как стек, снизу вверх, как этажность в многоквартирном доме, можно даже добавить этаж сверху и система нумерации не сломается. Как у вас этими полками обстоят дела?

Morgenh_and Sep 12 at 09:31

В многоквартирном доме первый этаж внизу, потому что люди попадают сначала туда. В комоде первая полка сверху, потому что люди сначала смотрят/открывают её

Iz_Leningrada Sep 13 at 09:48

Дела с этим так, что теперь придётся думать об этом...

malkovsky Sep 12 at 16:12

Если вы открываете словарь посередине и смотрите на первую букву пытаясь понять, должно ли ваше слово быть во второй половине или первой, а потом повторяете несколько раз - это бинарный поиск.
Возможно вы филолог и знаете, что слов на букву "а" больше, чем на букву "ы", а может даже знаете априорное распределение для первых, ну или просто осознаёте, что слово на букву "э" будет скорее в конце, чем в начала и смотрите не в середину, а куда-то еще основываясь на априорных знаниях, это интерполяционный поиск.
Возможно это ваш словарь и вы заранее сделали в нём закладки на начало каждой буквы, а может даже и на первые две буквы. Найдя таким образом нужный раздел вы совершили поразрядную сортировку.
Так или иначе в какой-то момент находите нужную страницу и какой-то слово, которое достаточно близко к искомому и уже просто пробегаетесь подряд назад или вперед -- это линейный поиск

Dimoyok Sep 13 at 08:05

Тут технари возразят, что вставки работают за O(N^2). И они будут правы, живя в дискретном мире ячеек памяти. В реальном мире мы запросто можем запихнуть футболку между двух других, не прилагая усилий для сдвига остальных.

Зависит же от структуры данных. Полка по типу хранения элементов похожа на массив, но по сложности вставки - на связный список)

microtheft Sep 13 at 14:12

Если у вас есть тысяча футболок, то у вас есть постельничий/я или лорд-хранитель футболок.

Pogro Sep 13 at 18:14

Тут технари возразят, что вставки работают за O(N^2)

Технарь возражает, сложность вставки в массив O(N).