Найти самые высокие 2 цифры - информатика

Question

Я пытаюсь найти алгоритм, чтобы найти самые высокие 2 числа в списке чисел.

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

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

Edit: Когда я говорю, п + LOG (п) я не имею в виду О (п + § п), а именно п + п войти

Answer 1

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

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

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

Answer 2

Как об этом:

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

Answer 3

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

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

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

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

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

Answer 4

Ответ отправил ShreevatsaR, кажется, O (n log n).

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

nickf имеет правильный ответ. В худшем случае список сортируется, он будет делать 2n сравнения - это O (n).

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

Answer 5

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

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

Answer 6

псевдокод (не это по существу п?)

int highestNum = 0 
int secondHighest = highestNum 

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