вопрос о сортировке

Question

Bubble sort в лучшем случае - O (n), в худшем - O (n ^ 2), а использование памяти - O (1). Сортировка слиянием всегда O (n log n), но ее использование памяти O (n).

Какой алгоритм мы бы использовали для реализации функции, которая принимает массив целых чисел и возвращает максимальное целое число в коллекции, предполагая, что длина массива меньше 1000. Что если длина массива больше 1000? 1003 *

Answer 1

Последовательное сканирование набора данных в поисках максимума может быть выполнено за O (n) время с использованием O (1) памяти.

Вы просто устанавливаете текущий максимум для первого элемента, затем пропускаете все остальные элементы, устанавливая текущий максимум на значение, если значение больше. Псевдо-код:

max = list[first_index]
for index = first_index+1 to last_index:
    if list[index] > max:
        max = list[index]

сложность не меняется независимо от количества элементов в списке, поэтому не имеет значения, сколько их есть.

---

Время работы , однако, изменится (поскольку алгоритм имеет время O (n)), и, если важно найти максимально быстрый, есть ряд возможностей. Все это зависит от выполнения работы, когда список изменяется , а не каждый раз, когда вам нужна информация, поэтому они лучше подходят для списка, который читается чаще, чем записывается, поэтому стоимость можно амортизировать.

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

Вариант 2 - пересчитать максимум (и количество элементов, удерживающих его) при вставке или удалении из списка. Изначально установите max на 0 и maxcount на 0 для пустого списка.

Для вставки:

• , если maxcount равно 0 (список пуст), установите max на это значение и maxcount на 1.
• в противном случае, если это значение больше max, установите max на это значение и maxcount на 1.
• в противном случае, если это значение равно max, добавьте 1 к maxcount.

Для удаления:

• , если это значение равно max, вычтите 1 из maxcount.
• затем, если maxcount равно 0, пересканируйте список, чтобы получить новые max и maxcount.

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

Answer 2

Максимальное значение всегда равно O (n), если оно не предварительно настроено. Если предварительно, это меньше. Сортировка перед поиском всегда хуже, чем O (n) ... поэтому, как правило, 1000 элементов потребуют 1000 сравнений ... просто сравните буквально Если работать с отсортированными структурами, это недорого. Если нет, то это дорого. Вставка с сортированными структурами дороже. ... вот почему это такая проблема.