Дихотомический поиск
 | Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( декабрь 2014 г. ) |
| Т – | М – – | – – – | Ч – – – – |
| ОН - - - · | |||
| Г – – · | В – – · – | ||
| С - - · · | |||
| Н – · | К – · – | И - · - - | |
| С – · – · | |||
| Д – · · | Х – · · – | ||
| Б – · · · | |||
| И · | А · – | В · - - | Дж · – – – |
| П · – – · | |||
| Р · – · | Ä · – · – | ||
| Л · – · · | |||
| Я · · | В · · - | О · · – – | |
| Ф · · – · | |||
| С · · · | V · · · – | ||
| Ч · · · · |
В информатике дихотомический поиск — это алгоритм поиска , который работает путем выбора между двумя различными альтернативами (дихотомиями). [1] или полихотомии [2] когда их больше двух) на каждом шаге. Это особый тип алгоритма «разделяй и властвуй» . Известный пример — двоичный поиск . [3]
Абстрактно, дихотомический поиск можно рассматривать как следование по ребрам неявной двоичной древовидной структуры до тех пор, пока она не достигнет листа (цели или конечного состояния). Это создает теоретический компромисс между количеством возможных состояний и временем выполнения: с учетом k сравнений алгоритм может достичь только O(2 к ) возможные состояния и/или возможные цели.
Некоторые дихотомические поиски дают результаты только на листьях дерева, например, дерево Хаффмана, используемое в кодировании Хаффмана , или дерево неявной классификации, используемое в «Двадцати вопросах» . Другие дихотомические поиски также дают результаты, по крайней мере, в некоторых внутренних узлах дерева, например, таблица дихотомического поиска для азбуки Морзе . Таким образом, в определении имеется некоторая расплывчатость. Хотя действительно может быть только два пути из любого узла, таким образом, на каждом шаге есть три возможности: выбрать один путь вперед или другой или остановиться на этом узле.
Дихотомический поиск часто используется в руководствах по ремонту, иногда графически иллюстрируемых блок-схемой, похожей на дерево неисправностей .
См. также
[ редактировать ]Внешние ссылки
[ редактировать ]Ссылки
[ редактировать ]- ^ «дихотомический поиск» . xlinux.nist.gov . Проверено 30 мая 2024 г.
- ^ «полихотомия» . xlinux.nist.gov . Проверено 30 мая 2024 г.
- ^ «Реализация двоичного поиска в Python: учебное пособие | Встроенный» . встроенный.com . Проверено 7 декабря 2023 г.
 | Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее . |