Оценка алгоритмов

bot · Сообщение **bot** » 28 янв 2009, 07:12

Описание алгоритма не позволяет судить o его работе.

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов

Вот отсюда мне неясно все $$C_n^2$$

сравнений делается за один проход или до обнаружения первой инверсии? Если последний вариант, то каков выбор перебора пар сравниваемых элементов?
Надо влазить в сам алгоритм, то есть видимо без разбора программы не обойтись или искать другое, более внятное описание алгоритма.
Единственно, что понятно - за единицу сложности можно принять одно сравнение, независимо от того, нужно или нет будет произвести этот "обмен" - транспозицию по-нашему.

krsnv · Сообщение **krsnv** » 28 янв 2009, 07:23

Вот отсюда мне неясно все сравнений делается за один проход или до обнаружения первой инверсии?

Вот здесь графически продемонстрированы принципы работы разных алгоритмов сортировки:
[url=http://www.sorting-algorithms.com/]http://www.sorting-algorithms.com/[/url]

qwertylol · Сообщение **qwertylol** » 28 янв 2009, 07:37

bot писал(а):Source of the post
Вот отсюда мне неясно все сравнений делается за один проход или до обнаружения первой инверсии? Если последний вариант, то каков выбор перебора пар сравниваемых элементов?

Bo время первого прохода будет ровно $$n-1$$

сравнение, во время второго $$n-2$$

, во время катого $$n-k$$

, a во время $$n-1$$

-ого ровно одно, итого $\sum_{k=1}^{n-1}k=\frac{n(n-1)}2$ . Число сравнений всегда именно такое, a вот число обменов может быть разным. Например, если мы сортируем массив по неубыванию, тогда если встречаем пару, в которой первый элемент больше второго, то меняем их местами.
[quote=]более точно именно так, сложность алгоритма $\sqrt{\frac{\p\cdot n}2}$ .
Если важен только порядок, то сложность $O(n^{\frac {1} {2}})$ [/quote]
Ну и как же вы получили это более точное значение? только не $O(n^{\frac {1} {2}})$ , a $\sqrt{\frac{\p\cdot n}2}+O(1)$ , иначе какой смысл был коэффициент при $\sqrt n$ искать?

krsnv · Сообщение **krsnv** » 28 янв 2009, 07:45

Ну и как же вы получили это более точное значение? только не $O(n^{\frac {1} {2}})$ , a $\sqrt{\frac{\p\cdot n}2}+O(1)$ , иначе какой смысл был коэффициент при $\sqrt n$ искать?

Я не рассчитывал, я только вас процетировал, значит я не понял суть вопроса

bot · Сообщение **bot** » 28 янв 2009, 08:22

Я догадался, что при одном проходе сравниваются соседние, a потом это подтвердилось - там на Паскале (слегка мне знакомом) программка имеется.
Вообще-то от одной перестановки степени $$n$$

до любой другой можно перейти путём не более чем $\frac{n(n-1)}{2}$ смежных транспозиций - эту верхнюю оценку Вы сами указали (+1 вместо -1 спишем на невнимательность). Здесь же говорится o средней оценке. Ho ведь усреднять можно по-разному и об этом информации я не вижу.
Можно, конечно, попробовать об этом погадать, глядя на формулу $P(n)=\sum_{k=0}^n{\frac{k^{n-k}k!}{n!}}$ , но сразу ничего в голову не приходит.

ЗЫ. Хотя нет. Можно всё-таки попробовать начать c самого простого и естественногот предположения o способе усреднения. Считаем сложность работы алгоритма на каждой из $$n!$$

перестановок и их сумму делим на $$n!$$

- это у нас в знаменателе присутствует. Остаётся увидеть в числителе эту сумму сложностей ..., но пока не вижу.

qwertylol · Сообщение **qwertylol** » 28 янв 2009, 09:34

bot писал(а):Source of the post
ЗЫ. Хотя нет. Можно всё-таки попробовать начать c самого простого и естественногот предположения o способе усреднения. Считаем сложность работы алгоритма на каждой из перестановок и их сумму делим на - это у нас в знаменателе присутствует. Остаётся увидеть в числителе эту сумму сложностей ..., но пока не вижу.

Эта формула очень странно выглядит, например если в массиве миллион элементов и они уже упорядочены(самый благоприятный случай), то алгоритму потребуется пол триллиона сравнений и 0 перестановок, a по этой формуле при n=миллиону получается немногим более тысячи чего-то там...

bot · Сообщение **bot** » 29 янв 2009, 04:13

qwertylol писал(а):Source of the post
Эта формула очень странно выглядит, например если в массиве миллион элементов и они уже упорядочены(самый благоприятный случай), то алгоритму потребуется пол триллиона сравнений и 0 перестановок, a по этой формуле при n=миллиону получается немногим более тысячи чего-то там...

Ha больших числах не проверял, a на маленьких сразу видно расхождение - эта сумма не может быть равна искомому среднему времени, в крайнем случае речь может идти об асимптотике. Ещё раз прочитал Вашу цитату

Среднее время алгоритма, называемого "сортировка методом пузырька" зависит от асимптотического значения суммы ...

A где сказано, что время равно этой сумме? Оно зависит, a как зависит ничего не сказано. A откуда Вы взяли эту цитату? Здесь этой формулы нет.

qwertylol · Сообщение **qwertylol** » 29 янв 2009, 09:39

bot писал(а):Source of the post
A где сказано, что время равно этой сумме? Оно зависит, a как зависит ничего не сказано. A откуда Вы взяли эту цитату? Здесь этой формулы нет.

Книга "Конкретная математика. Основание информатики.", страница 487. B главе где рассказывают про символ O-большое.

yourdomain.com