Big O обозначение для нескольких функций

Question

У меня есть вопрос, касающийся записи больших О, когда используется несколько функций. Допустим, я хочу узнать, какова сложность времени для следующего псевдокода:

heap sort array of size n
for i = 1 to n{
  retrieve array[i]
  change value of array[i]
}

Я знаю, что использование сортировки кучи - это O (n log (n)). Поскольку извлечение и изменение данных в массиве - это O (1), цикл имеет сложность O (n). Теперь мой вопрос: какова сложность этого кода в целом? Это просто самая большая временная сложность; O (n log (n)) в этом случае? Если это так, какова будет сложность функции, которая будет выглядеть следующим образом:

for i = 1 to n{
  // nothing fancy here
}
for y = 1 to n{
  // nothing fancy here either
}

Заранее спасибо.

Answer 1

for i = 1 to n{
  // nothing fancy here
}  //O(n)

for y = 1 to n{
  // nothing fancy here
}  //O(n)

Так что вместе это O(n) + O(n) = O(n).

Answer 2

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

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

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