Поиск 2-х наибольших чисел- информатика

Question

Я пытаюсь разработать алгоритм поиска 2-х самых высоких чисел в списке чисел.

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

Мой профессор задал нам домашнее задание написать алогритм, который находит 2 наибольших числа в n + log (n) сравнениях.Возможно ли это вообще?Есть какие-нибудь идеи, предложения?

Редактировать:Когда я говорю n + log (n), я имею в виду не O (n + log n), а именно n + log n

Answer 1

Да, это можно сделать не более чем (n + log n). Я действительно не могу сказать вам, как, не отдавая ответ, но позвольте мне попробовать. :-)

Возьмите n чисел, сравните их попарно. Возьмите ceil (n / 2) «победители» и повторите «как двоичное дерево». Вопросы: сколько сравнений нужно, чтобы найти самое большое? Сколько людей делает этот "победитель" победить? Кому мог проиграть второй по величине? Так сколько же сейчас нужно сравнений, чтобы найти второе по величине число?

Ответом оказывается всего n-1 + потолок (log n) - 1 сравнений, где журнал должен основываться на 2. Вы также можете доказать с помощью состязательного аргумента, что он в худшем случае невозможно добиться большего успеха, чем это.

Answer 2

Редактировать:Упс, пропустил простую вещь по глупости.Это решение неверно, хотя я сохраняю его здесь, поскольку оно по-прежнему является средним (n + log (n)).Спасибо Шривацару за то, что указал на мою глупость.Я рассматривал поиск по дереву, но совершенно упустил идею возврата, чтобы найти второе по величине число в журнале (n).

В любом случае, здесь следует мое доказательство того, почему низший алгоритм не более чем avg (n + log (n)).В реальной жизни это все равно должно работать, по крайней мере, довольно хорошо.

• Сначала сравните со вторым по величине зарегистрированным числом.
• Только в том случае, если это сравнение завершится успешно, сравните с наибольшим зарегистрированным числом.

Чтобы доказать, что это в среднем n + log n, нам просто нужно доказать, что первое сравнение выполняется в среднем только log (n) раз.И это довольно просто увидеть или продемонстрировать.

1. Предположим, что P - фактическая позиция текущего второго по величине числа в отсортированной версии списка, и запустите алгоритм
2. Если P>2, то при нахождении большего числа новое P в среднем будет не более P/ 2.
3. Если P= 2, то первое сравнение не может быть успешным, так как нет числа, которое было бы больше текущего второго по величине числа.
4. P может быть не более равно N
5. Из 2, 3 и 4 должно быть тривиально видно, что первое сравнение может быть успешным в среднем не более log (N) раз.

Answer 3

Как насчет этого?

for each listOfNumbers as number
    if number > secondHighest
        if number > highest
            secondHighest = highest
            highest = number
        else
            secondHighest = number

Answer 4

Ответ от ShreevatsaR выглядит как O (n log n).

Первый проход (n операций) дает n / 2 ответа. Повторяя, я полагаю, вы имеете в виду n / 2 операции для получения n / 4 ответов. Вы пройдете журнал циклов n раз. Это очень похоже на сортировку слиянием, за исключением того, что сортировка слиянием всегда обрабатывает n узлов каждый раз. Он также запускает журнал цикла n раз. И я не вижу, как этот алгоритм будет отслеживать второе по величине число.

Никф имеет правильный ответ. в худшем случае, когда список отсортирован, он выполнит 2n сравнений, то есть O (n).

Кстати, O (n + log n) - это O (n), обозначение Порядка относится к асимптотическому росту в худшем случае.

Answer 5

Вы можете использовать сортировку отсчетов, сортировку по основанию, сортировку по сегментам или другой алгоритм линейного времени, чтобы сначала отсортировать список в порядке убывания. Тогда просто получите первые 2 элемента отсортированного списка. Так что это займет (n) + 2 = (n)

Обратите внимание, что эти алгоритмы могут сортироваться по линейному времени, поскольку каждый из них имеет свои предположения.

Answer 6

Псевдокод (разве это не n?)

int highestNum = 0
int secondHighest = highestNum

for(i = 0; i < list.length; i++)
{
if(list[i] >= highestNum)
{
secondHighest = highestNum
highestNum = list[i]
}
}