Логарифмы и search algorithms

[Батька]

"If your algorithm halves the set of things it considers each time around the loop, then it is likely to be logarithmic, O(lg(n)). A binary search of a sorted list or traversing a binary tree can all be O(lg(n)).

Prove it."

Нормальный вопрос для выпускника австралийского вуза?
Собссно, понятно, что binary search не только likely to be O(lg(n)), а он и есть такой.
Насчет binary tree сейчас читаю, недоучили в школе...
А вообще, вопрос не очень понятный. Шо конкретно доказать требуется? Что у обоих алгоритмов эффективность может выражаться как функция O(lg(n))?
Кстати, lg - это log по основанию 2, кто помнит?

[shkoda]

lg это по степени 10 или десятичный
ln это по степени e или натуральный.
binary tree: a data structure in which each record may have two successors (children).

Требуется доказать, что бинарный поиск по сортировонному списку методом половинного деления имеет сложность O(lg(n)).
ИМХА копать в сторону пределов и геом прогрессий.

Вопрос уровня 2 курса наших ВУЗов. У нас это называлось "Структуры и алгоритмы обработки данных".

[Батька]

lg это по степени 10 или десятичный
ln это по степени e или натуральный.
binary tree: a data structure in which each record may have two successors (children).

Требуется доказать, что бинарный поиск по сортировонному списку методом половинного деления имеет сложность O(lg(n)).
ИМХА копать в сторону пределов и геом прогрессий.

Вопрос уровня 2 курса наших ВУЗов. У нас это называлось "Структуры и алгоритмы обработки данных".

Так то 2 курса НАШИХ вузов. А в местных мы главу про сложность пропустили.
Ок, врагу не сдается наш храбрый варяг. Буду гуглить дальше.

[Батька]

lg это по степени 10 или десятичный
ln это по степени e или натуральный.
binary tree: a data structure in which each record may have two successors (children).

Требуется доказать, что бинарный поиск по сортировонному списку методом половинного деления имеет сложность O(lg(n)).
ИМХА копать в сторону пределов и геом прогрессий.

Вопрос уровня 2 курса наших ВУЗов. У нас это называлось "Структуры и алгоритмы обработки данных".

Кстати,
"The binary logarithm is often used in computer science and information theory (where it is frequently written lg n ...)"
log без базы это, выходит, десятичный, а lg все-таки двоичный..

[shkoda]

Ну не мог же я забыть логарифмы за 10 лет
http://ru.wikipedia.org/wiki/Логарифм

[RomZes]

ну скажу в теории информации например, под логарифмом подразумевают log2

[Thur]

А разве O(Ln(n)) не будет таким же, как и O(Lg(n)) и вообще от основания логарифма оно не должно зависеть?

Я теорию специально не изучал, но вроде так должно быть из общих соображений.

[Батька]

Не знаю, что там от чего зависит, но док-во написала.

[Strannik]

а ты когда успела выпускником стать? и где это такие вопросы задают?

[Батька]

а ты когда успела выпускником стать? и где это такие вопросы задают?

Так неделю назад сессию отстреляла Работу искать начала, вот и задают вопросы, на С++ девелопера подаюсь. Кстати, вопрос задавали в Бри, так что это у вас там умники обитают.
О! Еще кстати, кому-то С++ девелопер начинающий нужен? У меня gpa 6.917, куча грамот и вообще я все налету хватаю.

[highlander]

О! Еще кстати, кому-то С++ девелопер начинающий нужен? У меня gpa 6.917, куча грамот и вообще я все налету хватаю.

Ну-ка, ну-ка - как посчитать факториал в compile-time?

А вопрос, КМК, глупый. Там все сводится к тому, что нужно вспомнить, что двоичный поиск или проход дерева как раз и половинит список на каждой итерации.

[Z1024]

Ну-ка, ну-ка - как посчитать факториал в compile-time?

Это неинтиресный вапрос, он в каждой книшке по шаблонам уже заезжен ))

[highlander]

Это неинтиресный вапрос, он в каждой книшке по шаблонам уже заезжен ))

Я бы дождался ответа, а потом слегка изменил условие

[Батька]

Это неинтиресный вапрос, он в каждой книшке по шаблонам уже заезжен ))

Я бы дождался ответа, а потом слегка изменил условие

Придется, видно, идти упаковщицей в Вуллис...

[RomZes]

как ответили на этот вопрос?

насколько я понял, нужно доказать, что все же сложность O(log2(n)) ?
Если у нас 128 комбинаций, то после первого прохода их станет 64, потом 32, потом 16, потом 8, потом 4, потом 2 и потом и все.


Вот и получаем log2(12 . верно?