В поисках 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)). Спасибо ShreevatsaR за указание на мою глупость. Я рассмотрел поиск по дереву, но совершенно упустил идею возврата назад, чтобы найти второе по величине число в log (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

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

int highestNum = 0
int secondHighest = highestNum

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

Answer 4

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

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

Answer 5

Ответ от 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 6

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

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