какова временная сложность этого кода и функции max?

Question

Дайте оценку big-O для числа операций, где операция представляет собой сравнение или умножение, используемое в этом сегменте алгоритма (игнорируя сравнения, используемые для проверки условий в циклах for, где a1, a2,..., положительные реальные цифры).Кроме того, функция max находит максимальное значение из индекса «i» в «j», а не сравнивает только два значения.

m := 0
for i := 1 to n
  for j := i + 1 to n
    m := max(ai, aj, m)

Проблема дает функцию max без описания.Функция получает три значения, «ai» - начальный индекс, «aj» - конечный, а «m» - переменная для сохранения максимального значения.Я думаю, что временная сложность функции равна O (n), потому что «A» - это просто массив, и мы должны пройти этот раздел, чтобы получить максимальное значение.Мы хотим знать, что это код bigO, а также функция max.

Answer 1

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

m := (highly negative number) -inf
for i := 1 to n
    m := max(ai,m)

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

Если быть более точным, временная сложность вашего алгоритма будет:

(n-1) + (n-2) + (n-3) + ... 1 = n *n - c (некоторая константа)

=> O (n2)