Время работы бинарного поиска. - есть ответ

Ответы:

kmike

1. никогда не слышал про тету(lg(n)), слышал про O(lg(n))
2. попробую доказать) за 1 итерацию(сравнение) список возможных вариантов уменьшается в 2 раза. Наша цель - 1 вариант. За x итераций мы можем, таким образом, выбрать точный вариант из 2^x (1*2*2*2*...*2) элементов. Пусть у нас n элементов. Тогда, чтобы найти x, решим уравнение 2^x=n. x=log2(n)=k*lg(n). Одна итерация занимает фикс. время, поэтому общее время t=k1*k2*lg(n)=A*lg(n), т.е. сложность алгоритма O(lg(n))

Alexknow

f(n) = Theta (g(n))
означает, что существуют c1, c2 > 0, n0, такие что
0 <= c1g(n) <= f(n) <= c2g(n) для всех n>n0

kmike

Выходит, наличие Omega(n) для бинарного поиска говорит о том, что быстрее, чем за логарифмическое время, поиск выполнить не удастся? но это же не так, т.к. минимальное время - константа, длительность 1й итерации

Mirraz7

Поиск за константу так же возможен, как сортировка за линейное время.

Roman Bolshakov

kmike, поиск за константу возможен, только это будет частным случаем. Т.к. время работы алгоритма c1*lg(n)+c2.

16 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.