В чем сложность этого алгоритма?

Question

procedure max (a[1..n]: integers)
    max := a[1]
    for i := 2 to n
        if max < a[i] then max := a[i]

Является ли сложность O(1) или O(n) наилучшим сценарием? Последовательность содержит n элементов. Это псевдокод.

Answer 1

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

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

Answer 2

Алгоритм O(n) в лучшем случае, в среднем и в худшем случае. Он также не работает , поскольку он относится только к a1 и использует < там, где следует использовать >.

Answer 3

Грубо говоря, O (1) означает, что независимо от размера ввода вы можете реализовать решение за фиксированное число шагов.

O (n) означает, что если у вас есть n входов, решение будет реализовано в шагах An (где A - это число, а не другая переменная). Понятно, что если у вас есть цикл for, который насчитывает от 2 до n, то есть n циклов, это означает, что если у вас есть входные элементы, ваш цикл будет считать от 2 до An, что означает, что он находится на том же уровне, что и вход, поэтому это O (n). Но вот каково линейное сканирование. :)

Answer 4

O (n) - вы должны отсканировать n элементов или коэффициент n (n / 2, n / 4 и т. Д.) - все еще O (n).

Answer 5

О (п)

вы можете получить O (1), если массив был отсортирован, поэтому вы просто вернете последний элемент.

но в случайно расположенных элементах лучший порядок для этой задачи - O (n)

Answer 6

Вы должны пройти весь массив. Таким образом, сложность будет O (n).

Answer 7

Если у вас есть код, который гласит:

for i := 2 to n

Тогда этот код будет O (n) в лучшем случае.

Мне любопытно, почему вы думаете, что это может быть постоянное время?