Поиск k максимальных элементов в столбце матрицы

[незваный гость]

О! Тогда Ваше объяснение:

esperanto писал(а):

Авторы имеют в виду алгоритм сложности tetta(n)

высоко содержательно.

Между прочим, когда я писал

незваный гость писал(а):

(Я не уверен, что авторы текста имеют в виду, не разбирался.)

я имел в виду, что мне не понятно, какую именно сложность авторы имеют в виду: среднюю, типичную, гарантированную,... а совсем не что значит «линейная» .

[esperanto]

незваный гость писал(а):

:evil:
О! Тогда Ваше объяснение:

esperanto писал(а):

Авторы имеют в виду алгоритм сложности tetta(n)

высоко содержательно.

Между прочим, когда я писал

незваный гость писал(а):

(Я не уверен, что авторы текста имеют в виду, не разбирался.)

я имел в виду, что мне не понятно, какую именно сложность авторы имеют в виду: среднюю, типичную, гарантированную,... а совсем не что значит «линейная» .

Тут ничего не поделать двусмысленность языка. Тем более что после вашего замечания ывы стали анализировать заведомо худший алгоритм, что и привело меня к выводу, что вы не поняли асимптотику предложенного авторами алгоритма Но если я вас правильно понял, то: Используя невероятностные алгоритм поиска порядковой статистики, получим алгоритм линейный от n и не зависящий от к. в худшем случае

Добавлено спустя 2 минуты 18 секунд:

Говорить о среднем тут не уместно, ибо не заданна функция распределения на входных данных

[Yuri Gendelman]

esperanto писал(а):

По-поводу последнего замечания вы не правы. Вот представте себе вы староста и заказываете врача в деревню.
Врач, первого типа не вылечит 10% больных и они умрут.
Врач второго типа, сможет оказать повторную помощь тем больным которых он не вылечил и уже в среднем 1\100 людей останется не вылечеными.

Да, согласен, Вы правы, если возможно многократное применение алгоритма на одних и тех же данных. Т.е. если врач второго типа успевает (ДО вскрытия ) распознать свою ошибку и поставить новый диагноз. Ваш пример мне понравился.

[незваный гость]

esperanto писал(а):

Говорить о среднем тут не уместно, ибо не заданна функция распределения на входных данных

А почему не уместно? Существует конечное число наборов данных, мы можем считать их равновероятными. И иметь ассимптотику, вполне полезную и заслуживающую доверия. Весьма полезную, если эта операция (поиск $k$ максимальных) повторяется множество раз.

Добавлено спустя 5 минут 37 секунд:

esperanto писал(а):

Первый метод, не прост(относительно) И описывается в книги Риверста.

А какой книге Риверста? Или как называется алгоритм?

[esperanto]

незваный гость писал(а):

:evil:

esperanto писал(а):

Говорить о среднем тут не уместно, ибо не заданна функция распределения на входных данных

А почему не уместно? Существует конечное число наборов данных, мы можем считать их равновероятными. И иметь ассимптотику, вполне полезную и заслуживающую доверия. Весьма полезную, если эта операция (поиск $k$ максимальных) повторяется множество раз.

Почему не уместно?


можно привести различные доводы, например,
Приведу пример.
Имеется граф на п-вершинах. Задача узнать есть ли в графе клика размером 0.01*log(n).

Алгоритм:
верни ответ такая клика есть.
конец

Такой алгоритм при равновероятном распределении на входных данных, ошибается с экспоненциально малой вероятностью. Алгоритм ошибается только на графах у которых нет клики, но при равновероятном распределении, доля таких графов экспоненциально мала. Т.е для n>1000 вероятность ошибки меньше вероятности того, что вселенная взорветься в конкретный момент. Например поэтому равновероятные оценки вызывают у меня предостережение.

Кроме того, зачастую данные задает противник, а в этом случае он даст наихудший случай. И в этом случае вероятностная быстрая сортировка, лучше быстрой невероятностной сортировки. Хотя в среднем они равна асимптотически.


с уважением

[незваный гость]

esperanto писал(а):

Приведу пример.

Простите, я не понял, как Ваш пример соотносится с моим вопросом. Я говорил о средней сложности, а не о средней правильности алгоритма.

Я не понял также насчет противника. Я обычно решаю задачи по программированию в условиях кооперирования с заказчиком. То есть данные никто намеренно не конструирует. Если же именно поведение в худшем случае важно (например, в real time), то выбираются алгоритмы с гарантированным худшим временем. Ну и что? Как это исключает оценку в среднем?

Впрочем, предположение о равновероятности начальных данных является сильным и, действительно, зависит от предметной области. Например, во многих практических случаях данные часто либо почти отсортированы в прямом либо обратном порядке. Но в MS-овской документации по STL формулировки совсем расплывчаты. А стандарт мне было (и есть) смотреть лень.

Я плохо понимаю термины «вероятностная» и «невероятностная» быстрые сортировки. Они, все-таки, не общепринятые (в отличии от быстрой сортировки (quicksort), которая, несмотря на вариации с выбором серднего элемента и другие, все таки хорошо определена — c пирамидальной или Шелла не спутаешь. И за сортировку слиянием не примешь.).

Кстати, не поленился я и слазить в перый том Фихтенгольца. Обозначения $\Theta$ там нет, зато такие величины он обозначает как эквивалентные $\sim$ (а более высокий порядок обозначает как ${\rm o}()$). Кнут же использует именно ${\rm O}$ как обозначение эквивалентной величины. Так что резонный вопрос — откуда дровишки (обозначения)?

[esperanto]

незваный гость писал(а):

Кстати, не поленился я и слазить в перый том Фихтенгольца. Обозначения $\Theta$ там нет, зато такие величины он обозначает как эквивалентные $\sim$ (а более высокий порядок обозначает как ${\rm o}()$). Кнут же использует именно ${\rm O}$ как обозначение эквивалентной величины. Так что резонный вопрос — откуда дровишки (обозначения)?


А какой книге Риверста? Или как называется алгоритм?

http://en.wikipedia.org/wiki/Big_O_notation
Мне кажется нотация была введена в том виде в каком она есть сейчас, уже после Фихтенгольца.
"Использование тетта обозначений рекомендована Кнутом" - Алгоритмы построение и анализ Кормен, Риверст, Лейзерсон - втророе издание


Добавлено спустя 2 минуты 38 секунд:

незваный гость писал(а):

:

Я плохо понимаю термины «вероятностная» и «невероятностная» быстрые сортировки. Они, все-таки, не общепринятые (в отличии от быстрой сортировки (quicksort), которая, несмотря на вариации с выбором серднего элемента и другие, все таки хорошо определена — c пирамидальной или Шелла не спутаешь. И за сортировку слиянием не примешь.).

Another common choice is to randomly choose a pivot index, typically using a pseudorandom number generator. If the numbers are truly random, it can be proven that the resulting algorithm, called randomized quicksort, runs in an expected time of Θ(n log n)
http://en.wikipedia.org/wiki/Quicksort

Добавлено спустя 8 минут 57 секунд:

незваный гость писал(а):

: Простите, я не понял, как Ваш пример соотносится с моим вопросом. Я говорил о средней сложности, а не о средней правильности алгоритма.
)?

Нельзя привести доказательство, почему не стоит полагаться на равномерность распределения. Можно лишь дать примеры так или иначе связаные с вопросом.
Я привел пример того, что при равновероятном распределении на входах и очень маленькой ошибке, многие алгоритмы можно вообще не писать, ибо вероятность получить плохие данные будет пренебрежимо мала

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

[незваный гость]

Спасибо за развернутый ответ и ссылки. Мы-таки говорили на разных языках. Теперь я Вас понимаю.

esperanto писал(а):

"Использование тетта обозначений рекомендована Кнутом"

Cormen, Leiserson, Rivest писал(а):

Knuth [182] traces the origin of the O-notation to a number-theory text by P. Bachmann in 1892. The o-notation was invented by E. Landau in 1909 for his discussion of the distribution of prime numbers. The Ω and Θ notations were advocated by Knuth [186] to correct the popular, but technically sloppy, practice in the literature of using O-notation for both upper and lower bounds. Many people continue to use the O-notation where the Θ-notation is more technically precise. Further discussion of the history and development of asymptotic notations can be found in Knuth [182, 186] and Brassard and Bratley [46].

Я пытаюсь найти статью Кнута, на которую ссылается википедия. Но мне тем более интересно: использование ${\rm O}$ в русском издании «Искусства программирования на ЭВМ» — это артефакт перевода или так в оригинале (оригинал я тоже попробую найти, но это, скорее всего, займет больше времени)? (Впрочем, первое издание «Искусства программирования» вышло до этой «основопологающей» статьи, и, видимо, Кнут не счел нужным менять текст книги.)

[to advocate — отстаивать, защищать, пропагандировать. Похоже, еще один артефакт перевода]

esperanto писал(а):

called randomized quicksort

Я бы скорее перевел как рандомизированная быстрая сортировка. Вероятностная — это что-то probabilistic. Это что, принятый перевод?

esperanto писал(а):

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

Ну разумеется, говоря о среднем, формально говорят с уточнением о принимаемом распределении данных. Но для данных обычно известно характерное, наиболее популярное распределение. Скажем, средняя величина выигрыша при 10000 бросаниях монетки будет распределена по Гауссу (по Стьюденту), но сама последовательность — равномерно (особенно, если монетка честная). И так далее. Почему же нельзя говорить о среднем времени сортировки, предполагая равную вероятность входных последовательностей? Можно, явно оговаривая это. И никаких двусмысленностей не возникает. Хотя предполагать равномерное распределение не всегда уместно.

Ваш же исходный пример мне живо напоминает анекдот о малолетнем гении из деткого сада: на любой, сколь угодно сложный, вопрос (допускающий ответ да-нет) он отвечает правильно в целых 50% случаев! Все-таки правильность в среднем сродни средней температуре по больнице (включая морг) — корректна, но не информативна. В отличии от среднего времени работы, которое значимо.

Кстати, о сортировке и примерах. Мне пришлось как-то раз поучать студента, который проверял правильность ответа путем проверки упорядочивания результата. Я порекомендовал ему сортировку за линейное время — записывать в ответ 1, 2, 3,… Его критерию правильности удовлетворяло.