Я смущен, является ли линейный поиск или бинарный поиск более эффективным при работе и хранении.Какая эффективность и эффективность во время работы эффективны в алогариме?
Поводу объяснений действительно оценили
@Trophe покрыл сложность времени, поэтому я попытаюсь объяснить пространство сложности,
Требование пространства имеет ту же сложность
линейный поиск является проще и требует только одна переменной
бинарные должно хранить нижнюю и верхнюю границу, так что более пространство, но это не зависит от размера списка
Таким образом, мы говорим, что они представляют собой как O (1) пространственную сложность
линейный поиск начинается с начала и сравнивает каждый элемент до тех пор, пока не найдет то, что вы ищете.
Бинарный поиск разбивает список посередине и выглядит, если ваше значение больше или меньше значения поворота. Затем он продолжает делать это рекурсивно.
0 Например, Список людей. Вы ищете Джона. Бинарный поиск выглядит посреди списка и может найти Mark. Джон ниже, поэтому поиск отбрасывает верхнюю половину списка, так как Джон не будет в нем и повторяет это в нижней половине (рекурсия)
Бинарный поиск намного эффективнее, но список должен быть отсортирован.
Однако - сортировка списка происходит медленнее, чем линейный поиск. Вы не выигрываете в эффективности, сначала сортируя несортированный список.
Зависит от того, сколько раз вы будете искать список, если это всегда так, никто никогда не будет сортировать список. –
@ Jake Продавцы: Да, хорошая точка. Хорошим примером является адресная книга. Вероятно, вы будете искать гораздо чаще, чем добавлять новых людей. – Christoffer
Конечно, бинарный поиск более эффективен, если список уже отсортирован по алгоритму 'O (log N), а линейный поиск принимает значение O (N) 'для сортированных и несортированных данных. Для отсортированных данных используется двоичный поиск, для несортированных данных используется линейный поиск. –
Похожие сообщения: [что означает O (N)] (http://stackoverflow.com/questions/1909307/what-does-on-mean), [Что означает O (log n)?] (Http: //stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly) –
Если бы вы потратили пару минут до публикации, чтобы прочитать первые несколько предложений соответствующих статей в Википедии ([linear] (http : //en.wikipedia.org/wiki/Linear_search), [binary] (http://en.wikipedia.org/wiki/Binary_search)), вы бы увидели это: _... Поэтому, если в списке больше чем несколько элементов, другие методы (такие как ** бинарный поиск или хеширование) будут быстрее **, но они также налагают дополнительные требования. – DaoWen