Каким будет время работы построения кучи?

Question

[isxaker]

Каким будет время работы построения кучи, если просто последовательно добавить в кучу все n элементов?

Answer 1

[Владимир Петриго]

Скорее всего ответы
Ω(nlogn)
O(nlogn)
Так как для создания пустого массива и помещения туда последовательно элементов займет время O(n) + для поддержания свойств кучи (процесс просеивания) потребуется в худшем случае O(logn).
Но так как требуется выбрать все подходящие варианты, то:
Ω(n) - так как функция будет расти не медленнее.
И O(n^2) так как сверху функция ограничена n^2.

Answer 2

[Mrrl]

О(N*log(N)). Для каждого из последних N/2 элементов нужно примерно по log(N) операций.
Вот построить кучу, переставляя элементы уже заполненного массива, можно за O(N) операций.

Comments

[isxaker]

@Mrrl я тоже считаю, что O(n*logn). Мне нужно выбрать все верные варианты из следующих
O(n)
Ω(n2)
Ω(n)
O(n2)
Ω(nlogn)
O(nlogn)

[isxaker]

Мне кажется, что я уже все перепробовал =(

[isxaker]

Я считаю, что правильный ответ
1. Лучший Ω(n)
2. Худший O(nlogn)

Но это тоже не верно

[Mrrl]

Никогда не понимал этих омега и тета. На всякий случай, попробуйте набор Ω(n), O(n^2), O(nlogn), Ω(nlogn) (в последней я не уверен).

[Миша Кринкин]

@isxaker ну если O(nlogn), то автоматически и O(n2) (если это n в квадрате)

Answer 3

[throughtheether]

Каким будет время работы построения кучи, если просто последовательно добавить в кучу все n элементов?

Мне нужно выбрать все верные варианты из следующих
O(n)
Ω(n2)
Ω(n)
O(n2)
Ω(nlogn)
O(nlogn)

Если мы последовательно добавляем элементы (всего их n) в кучу (бинарную кучу) и каждый раз восстанавливаем свойство кучи (верхняя оценка сложности O(logn), нижняя оценка Ω(1)), то верхняя оценка общей сложности будет O(nlogn), нижняя - Ω(n). Правильные варианты, на мой взгляд:
Ω(n), O(n2) (если имеется в виду O(n*n)),O(nlogn)

Answer 4

[overmes]

сложность будет N

Comments

[isxaker]

@overmes в лучшем случае