White Owl
SSБД содержит 10^4 записей в отсортированном порядке. 60% записей используются часто, остальные 40% редко.

Ну как же вы так? Ай-ай-ай! В нашей профессии английский надо знать как родной.
"10К имен, из которых 40% известны как "хорошие клиенты" и кто совместно генерирует 60% запросов к базе"

Моё перевод упрощён, но корректен.
Дословный перевод будет такой:
База данных содержит 10^4 отсортированных имён. (Далее идём of whom, значит 'которых') 40% известны как хорошие клиенты(имена и клиенты в данном случае синонимы) и на них совместно приходится 60% запросов к базе данных. И т.д.

White OwlSashaMercury 4 -30
БД содержит 10^4 записей в отсортированном порядке. 60% записей используются часто, остальные 40% редко.Не совсем. Там имеется 40% людей которые делают 60% запросов.
Это значит что результат поиска "своей" записи надо умножить на частоту обращений.

SashaMercuryQ3) Решение третьей задачи кажется совсем простым. В первом случае нужно задать такой вопрос, что лучше, log(n) или 2log(n) ? Конечно лучше хранить всё в одномерном упорядоченном массиве и использовать двоичный поиск.
Не совсем... К тому же у нас заранее известен n.
В случае одного общего массива мы имеем: 10000*log(10000)=132877.1238.
А в случае двух массивов мы имеем: 6000*log(4000) + 4000*log(6000)=71794.7057 + 50202.9871 = 121997.6928
Итого, два массива при бинарном поиске получаются чуть-чуть получше, примерно на 8%.

Аналогично для линейного:
Общий массив: 10К * 10К = 100М
Два массива: 6К*4К+4К*6К= 24К+24К = 48К
Выигрыш получается еще больше.

Я выделил красным то место где вы опечатались(или ошиблись, но это повлияло на результат).
1. 1 Пусть у нас один упорядоченный массив из 10000, бинарный поиск даст нам высоту 14. Пусть мы имеем к запросов, итого 14k затрат.
1. 2. Пусть у нас два упорядоченных массива. Первый 4000 элементов, высота поиска 12, второй 6000 элементов, высота 13. Пусть у нас 0,6k запросов на первый массив, 0,4k запросов проходят через первый массив и переходят на второй. Имеем k*(0,6*12+0,4*(12+13))=17,2k затрат.
Вывод: в данном конкретном случае, с точки зрения поиска, нет смысла разделять два упорядоченных массива. Но данный анализ неполный, ибо не учтены остальные аспекты, и я не знаю как правильно это сделать.

White OwlSashaMercuryQ2) Со второй задачей сложнее. Очевидным был бы следующий ответ: Так как Extract Maximum выполняется за O(1) то в таком случае сортировка возможна за O(n). Но 1. Зачем остальные части условия ? 2. Разве существует доказательство того что сортировка не может быть реализована за O(n) ?
Следовательно рассуждаю я скорее всего неверно(при решении данной задачи). Есть ли у вас какие-то идеи ?Тоже не понял, к чему там подсказка. Я рассуждаю так:
а) Если в структуре данных хранится несколько элементов, то эта структура может рассматриваться как массив. В дальнейшем буду использовать это слово и сопутствующую терминологию.
б) Чтобы операция Maximum выполнялась за O(1), надо чтобы в данном массиве данных максимальный элемент был всегда четко указан. Это можно сделать двумя способами, либо хранить дополнительно индекс максимального элемента, либо держать в массив в сортированном состоянии.
в) Если массив изначально не сортирован, но мы имеем индекс на его максимальный элемент то чтобы выполнялась операция ExtractMaximum выполнялась за O(1) надо чтобы мы могли за O(1) найти новый максимальный элемент после экстракта предыдущего максимума. Значит нам нужно где-то хранить индекс предыдущего во величине элемента. Это проще всего сделать если хранить индекс предыдущего элемента вместе с самим элементами... Вывод - в случае хранения данных не в сортированном виде мы должны хранить его в связном списке.
г) Но в случае связанного списка для вставки элемента в правильное место (что бы сохранить сортированность списка), нам понадобится это место найти, а это уже обязательно O(n).
д) Если данные хранятся в виде сортированного индексированного массива, то для нахождения максимума достаточно взять его последний элемент, а для нахождения предыдущего максимально - предпоследний. Все просто и легко, Maximum и ExtractMaximum выполняются за O(1).
е) А если у нас сортированный индексированный массив, то операция вставки потребует найти те два элемента между которыми надо вставлять новый, а это как минимум O(log n). А потом еще двигать хвост массива чтобы освободить место под новый элемент, а это еще O(n).
Таким образом у нас и получается что структура данных у которой все три завяленные операции выполняются за O(1) не получается...

Теперь я понял при чём тут вставка. Всё что вы рассказали выглядит логично.
Однако это не доказывает того, что такое в принципе не возможно. И вообще, я не уверен в том, что существует полное и объективное доказательство такого факта. Вероятно автор имел ввиду рассуждение в вашем ключе. Спасибо :)

Dima TWhite Owlпропущено...
Не совсем. Там имеется 40% людей которые делают 60% запросов.
Неверный вывод. Сказано "часто", без конкретики, я так понимаю это точно не 60:40, может 100:1 или 1000:1

Дмитрий, тут я виноват, не до конца перевёл. Но связано это с тем, что частота запросов на мой взгляд не должна сильно влиять на базу данных. Если критерием сравнения будет вставка, то только при отношении около 17:3 преимущество будет у второго способа(2 бинарных поиска)

tchingiz,
в формуле для сферы попробуйте заменить большую полуось а, на сумму большой a и малой b полуосей эллипсоида делённых на два. a -> (a+b)/2.

Вообще для таких вещей используют интегральное исчисление. Не знаю насколько вам это подходит

Нет, приближенная формула другая.
У вас , далее посмотрите приближенные формулы для полупериметра.
Либо, периметр можно найти как длину кривой, в вашем случае так:

Что значит радиус линии, подразумевается радиус кривой ? Вы использовали эту формулу, она вам подходит ?

Програмёр,

Проблема с шагом 3. Вероятность попадания нового элемента 10/12, остаться старому 10/11 * 11/12 = 10/12

tchingiz,
предлагал использовать интеграл, но это видимо не очень удобно. А зачем в вашем случае альтернатива, если вы уже всё сделали ?

Програмёр, бывает, мне даже жаль что вы ошиблись, ибо кое-что мне в том алгоритме действительно не нравится, я позже писал