Почему самое быстрое время выполнения CompareToAll - O (1)?

Question

в Реализации получить максимальное число в массиве, используя методологию CompareToAll с расширением не сравнения каждого числа с любым другим числом, а сравнения каждого числа только с числами, встречающимися после него. По сути, каждое число перед текущим номером уже сравнивается с текущим числом. Таким образом, алгоритм остается верным, если сравнивать только числа, встречающиеся после текущего числа. Теперь я понимаю, почему наихудшее время для этого - O (n2) O ("n квадрат") Но я не могу понять, почему самое быстрое время работы - O (1).

Полагаю, в лучшем случае оно должно быть равно O (n) Анализ Big-O для лучшего случая скопирован с

Answer 1

Для отсортированного массива самое быстрое время - O (1), потому что вы можете просто выбрать первый или последний элемент в зависимости от направления сортировки. Однако для несортированного массива я не могу предвидеть какой-либо алгоритм, который может найти максимум за время меньше чем O (n).

Почему: предположим, у нас есть массив с n элементами неизвестного порядка. Выберите первый элемент; потенциально это макс. Однако как вы узнаете, что второй элемент не является максимальным? Вам придется проверить это. Точно так же, как вы узнали, что третий элемент не является максимальным? И так далее, к n тестам.

Answer 2

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

Вам нужно сравнить каждое число только один раз с предыдущим максимумом. Это код в Python:

def max(a):
    assert len(a) > 0
    current = a[0]
    for x in a[1:]:
       if x > current: current = x
    return current