Как доказать, что количество инверсий в куче в наихудшем случае равно Ω(nlogn)?

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

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


performance analysis algorithm heap
person htdahms    schedule 09.06.2010    source источник
comment
а сложность порядка, если сортировка вставками - какая?   -  person sth    schedule 09.06.2010
comment
Это все, что они вам дают. Скопирую/вставил вопрос. Но если я правильно помню, сортировка вставками в кучах - это O(n^2)?   -  person htdahms    schedule 09.06.2010
comment
Как куча может иметь инверсии? Определение кучи предотвращает вертикальное нарушение порядка элементов. Вы имеете в виду инверсии в базовом массиве, на который отображается куча, или что-то в этом роде?   -  person Craig Gidney    schedule 09.06.2010

Ответы (1)


arrow_upward
2
arrow_downward

Сложность сортировки вставками составляет O(n+d), где d — количество инверсионных пар.

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

person Community    schedule 09.06.2010
comment
Я думаю, это вопрос: что это говорит? :) - person IVlad; 09.06.2010
comment
@|Влад: Мне действительно нужно это объяснять? Смайлик заставляет меня думать, что вы шутите, но отсутствие голосов заставляет меня думать, что вы серьезно ;-) :-P - person ; 09.06.2010
comment
@Moron - лично я понял это, но я думаю, что для ОП было бы неплохо получить больше подробностей. Нравится, что означают Omega и Theta и как они помогают добиться результата. - person IVlad; 09.06.2010
comment
@IVlad: Я полагаю, что OP понимает, что означают эти термины, поскольку он готовится к экзамену, и это один из вопросов предыдущего экзамена! Я намеренно оставил его незавершенным, так как отнесся к этому как к «почти домашнему заданию». Если ОП вернется с просьбой о разъяснении, я предоставлю их, но только после того, как они сами приложат некоторые усилия. - person ; 09.06.2010
comment
Сейчас я просматриваю другие бумаги. Но я знаю, что они означают. Спасибо, я думаю, что я понял это сейчас, но напишу позже, чтобы быть уверенным. :) - person htdahms; 10.06.2010