Алгоритмы для жизни: Простые способы принимать верные решения - [28]
Однако с сортировкой ситуация абсолютно противоположная: при росте количества разновидностей «себестоимость единицы сортировки возрастает». Сортировка предполагает существенный рост внешних издержек при увеличении масштаба, ломая наши стандартные представления о преимуществах работы с большими объемами.
Приготовить ужин для двоих обычно не сложнее, чем для одного, и это однозначно проще, чем готовить ужин на одну персону дважды. Но сортировка, скажем, ста книг на одной книжной полке займет у вас гораздо больше времени, чем сортировка двух полок, на каждой из которых стоит по пятьдесят книг. У вас в два раза больше объектов для сортировки и в два раза больше места, на которое можно поставить тот или иной объект. Чем глобальней ваша задача, тем хуже. Это самое первое и наиболее фундаментальное наблюдение о теории сортировки. Масштаб убивает.
Из этого следует: чтобы уменьшить боль и страдания, нам необходимо сократить количество вещей для сортировки.
Это факт: одна из лучших превентивных мер во избежание трудностей с подсчетами при сортировке носков – просто стирать их почаще. Если заниматься стиркой в три раза чаще, можно сократить затраты на вычисления в девять раз.
Действительно, если бы сосед Хиллиса следовал своей излюбленной процедуре, но сократил бы перерыв между стирками с 14 дней до 13, одно это могло бы сэкономить ему 28 «вытягиваний» носков из корзины. (А если бы он увеличил интервал между стирками на день, ему пришлось бы «вылавливать» пару лишние 30 раз.)
Даже на примере такой несложной работы, регулярно проделываемой раз в две недели, мы видим, что масштабы сортировки понемногу становятся в тягость.
В то же время компьютерам приходится регулярно сортировать миллионы различных единиц информации за раз. Для этого, как сказал герой фильма «Челюсти», нам понадобится лодка побольше – и алгоритм получше. Но, чтобы ответить на вопросы, как мы должны осуществлять сортировку и какие ее методы наиболее эффективны, нам необходимо прежде всего решить, как мы будем производить учет.
«О» большое: эталон для худшего случая
Чешский иллюзионист Зденек Брадак попал в Книгу рекордов Гиннесса, установив рекорд по сортировке колоды карт. 15 мая 2008 года Брадак смог разложить в правильном порядке колоду из 52 карт всего за 36,16 секунды[7]. Как ему это удалось? Какую технику сортировки он применял? И хотя его ответ, очевидно, пролил бы свет на теорию сортировки, сам Брадак воздержался от комментария. Мы, несомненно, уважаем мастерство и ловкость маэстро, но при этом мы на 100 % уверены, что можем побить его рекорд. По сути, мы уверены на 100 %, что можем поставить рекорд, который никто не сможет побить. Все, что нам нужно, – это около 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000 попыток в борьбе за звание рекордсмена. Это число, значение которого немного больше 80 унвигинтиллионов (52 факториал, или 52! в математическом обозначении), – число возможных перестановок в колоде карт. Предпринимая такое количество попыток, вы рано или поздно обязательно сложите колоду в правильном порядке, при этом абсолютно случайно. Таким образом, теперь мы можем с гордостью вписать в Книгу рекордов Гиннесса имя Кристиана Гриффитса, выступившего с не таким уж и плохим временем – 0 минут 0 секунд. По правде говоря, таким способом мы бы точно пытались установить новый рекорд до конца света. Тем не менее этот факт явно указывает на огромные фундаментальные различия между рекордсменами и учеными-компьютерщиками. Именитые господа из Книги рекордов Гиннесса беспокоятся только о показателях в наилучшем случае. Конечно, едва ли их можно винить за это, ведь все спортивные рекорды – не что иное, как показатели одного лучшего выступления. Однако информатику практически никогда не волнует наилучший случай. Вместо этого ученые хотели бы знать, сколько в среднем занимает тасование карт у того же Брадака: было бы здорово заставить его тасовать колоду все 80 унвигинтиллионов раз (или что-то в этом роде) и оценивать его по средней скорости на протяжении всех попыток (теперь вы понимаете, почему программистов не допускают до таких вещей).
Более того, специалисту по информатике было бы интересно узнать и наихудшее время при тасовании колоды. Анализ наихудшего случая позволяет нам получить четкие гарантии, что процесс в принципе конечен, что срок исполнения задачи не будет сорван.
Таким образом, до конца этой главы, да и, пожалуй, всей книги мы будем обсуждать действие алгоритмов в наихудших случаях, если не указано иное.
В программировании есть обозначение, придуманное специально для определения сценария алгоритма в наихудшем случае. Это прописная «О», или «О большое». За понятием «О большого» стоит одна небольшая хитрость, которая с первого взгляда не совсем очевидна. Суть в том, что «О большое» не столько выражает действие алгоритма в минутах и секундах, сколько может характеризовать тип взаимосвязи между размером задачи и временем, потраченным на ее решение. Поскольку «О большое» намеренно проливает свет на некоторые важные детали, перед нами появляется схема разделения задач на различные широкие категории.
В монографии представлен аналитический обзор современной литературы, отражающий основные научные подходы к изучению родственников больных с аддиктивными расстройствами. В работе описываются особенности личностного и семейного функционирования различных категорий родственников больных, страдающих героиновой наркоманией, в сопоставлении с показателями их сверстников из нормативной выборки. Нормативная группа включала практически здоровых лиц, не имеющих выраженных нарушений социальной адаптации. Среди членов семьи нормативной группы отсутствовали лица, страдающие наркотической зависимостью, выраженными нервно-психическими или тяжелыми хроническими соматическими заболеваниями. Описан характер семейной и личностной дисфункциональности родственников наркозависимых, в частности, среди показателей семейного функционирования особое внимание уделено таким, как: нарушение семейного климата и уровня организации семьи, снижение показателей семейной социокультурной ориентации.
Успешность – это реальность или призрак? Ради неё многие люди готовы на всё! Но как её достичь? Использовать логику или довериться случаю? Эта книга поможет достичь подлинной успешности и счастья в жизни! Почему бы не начать её читать? Несомненно вы найдёте много полезного для своей жизни!
Соционическое знание дает конкретные рекомендации, как произвести впечатление и строить отношения с каждым из 16 типов мужчин. Соционика избавит вас от необходимости прибегать к методу ненаучного тыка в надежде, что хоть какое-нибудь из ваших достоинств случайно впечатлит и не напугает при этом вашего партнера.
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
«По моему мнению, Майкл Гриндер изложил нечто экстраординарное в этой книге. Он прекрасно представил некоторые репрезентативные паттерны, смоделированные в НЛП – технологии, и существенно усовершенствовал их для конкретного контекста образования. Читателю представлены точные описания техник активного и пассивного наблюдений, классификация стилей научения учеников и техники адаптации учителя к ученику. Результат – не только улучшение успеваемости, но и улучшение взаимоотношений с учениками. Поэтому я с удовольствием рекомендую всем, кто хочет самосовершенствоваться, овладеть паттернами, представленными в этой книге.
«Кокология» – модная японская игра, представляющая собой серию увлекательных психологических тестов, – входит сегодня в число популярнейших американских бестселлеров. «Кокология-2» предлагает читателям более 50 совершенно новых тестов, рассчитанных как на опытных кокологов, так и на новичков. Кокология – наука, занимающаяся изучением кокоро, что по-японски значит «ум» или «дух», – предлагает вам совершенно безобидные на первый взгляд вопросы вроде «Какая комната в вашем воображаемом доме самая чистая?», после чего выдает на основе полученных ответов описание вашего характера, ваших помыслов и предпочтений.