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

qwertylol · Сообщение **qwertylol** » 27 янв 2009, 23:43

Меня давно мучает вопрос- как дают оценки алгоритмам?
Для примера возьмём пузырьковую сортировку(что может быть проще?). Вот c чего они взяли, что сложность именно $$O(x^2)$$

(в сети легко найти и более точные оценки)? Обычно оценивают суммы или интегралы, a тут алгоритмы...

venja · Сообщение **venja** » 28 янв 2009, 05:39

Обычно оценивают порядок числа арифметических действий при реализации алгоритма c заданной точностью.

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

venja писал(а):Source of the post
Обычно оценивают порядок числа арифметических действий при реализации алгоритма c заданной точностью.

Ну тогда в этом примере сложность нуль . Тут ведь арифметики нет :no: .

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

Скажем в пузыре максимум может быть $\frac{n\cdot(n+1)}2$ сравнений(как раз $$O(n^2)$$

) и столько же обменов. Ho в той же сортировке выбором сложность указана такая же, хотя обменов там ровно $$n-1$$

.

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

qwertylol писал(а):Source of the post
Ho в той же сортировке выбором сложность указана такая же, хотя обменов там ровно .

B сортировке выбором сравнений $$O(n^2)$$

, обменов

, поэтому общая сложность алгоритма $$O(n^2)$$

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

Странно, что это за алгоритм совсем без арифметики? Впрочем вместо арифметики могут быть другие действия, к примеру булевы. B пузырьковых камерах я совсем не разбираюсь, возьму другой пример. Требуется сравнить сложность нахождения решения крамеровской систему по двум алгоритмам:
1) по формуле Крамера
2) методом гауссовых исключений
B первом случае число действий прикидываем опять же по алгоритму вычисления определителя методом гауссовых вычислений.

За единицу сложности примем элементарную операцию $x\odot y = \lambda x + y$ выполняемую над числами $$x$$

и

при любом фиксированном $\lambda$ .
При нахождении одного определителя приводим его к треугольному виду - это потребует $$n-1$$

действий над $$n-$$

мерными массивами плюс $$n-2$$

действий над $$n-1-$$

мерными массивами плюс ...
Итого получаем $(n-1)n+(n-2)(n-1)+... \sim \frac{n^2}{6}$ элементарных действий.
Всего надо сосчитать $$n+1$$

определителей, стало быть сложность $\sim \frac{n^3}{6}$

По второму алгоритму треугольного вида мало - надо сделать прямой ход и обратный ход над $$n+1-$$

мерными массивами. $$+1$$

на асимтотику не влияет, a упрощением обратного хода из-за появления нижних нулей пренебрежём и отнесём в пользу бедных - первого алгоритма. Итого сложность второго алгоритма $\sim 2\cdot \frac{n^2}{6}=\cdot \frac{n^2}{3}$
C переходом к O большим множитель отбрасывается и получаем соответственно $$O(n^3)$$

и

, то есть при достаточно больших $$n$$

второй алгоритм лучше.
Ha практике так и есть - при $$n=2$$

как правило лучше по Крамеру, при $$n=3$$

вопрос довольно спорный, так как конкретность чисел может внести значительные коррективы в оценку, a вот при $$n>3$$

уже трудно будет привести пример, где по Крамеру легче.

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

bot, большое спасибо за объяснение, но здесь видите в чём проблема- непонятно, что берут за "единицу сложности". Вот цитата из книги "Конкретная математика. Основание информатики":

Среднее время алгоритма, называемого "сортировка методом пузырька" зависит от асимптотического значения суммы $P(n)=\sum_{k=0}^n{\frac{k^{n-k}k!}{n!}}$ .

Откуда эта сумма взялась авторы, увы, умолчали .
A на описание метода пузырька я оставлял ссылку в первом посте и к пузырьковым камерам он отношения не имеет . Это простейший алгоритм сортировки и умещается он в пару строк(потому я его и выбрал).
[url=http://ru.wikipedia.org/wiki/Сортировка_пузырьком]http://ru.wikipedia.org/wiki/Сортир\xD0...\x83зырьком[/url]

B сортировке выбором сравнений , обменов , поэтому общая сложность алгоритма

Ну допустим всё так, тогда каким образом мне оценить алгоритм более точно( $\sqrt{\frac{\p\cdot n}2}$ )?

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

что берут за "единицу сложности"?

Часто в статьях приходилось видеть отдельную оценку сложностей алгоритма по разным операциям, например:
$$O(n^3)$$

- операций сравнения
$$O(n^2)$$

- операций сложения

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

krsnv писал(а):Source of the post
Часто в статьях приходилось видеть отдельную оценку сложностей алгоритма по разным операциям, например:
- операций сравнения
- операций сложения

Меня интересует именно время выполнения алгоритма и везде имелось ввиду именно это.

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

тогда каким образом мне оценить алгоритм более точно( $\sqrt{\frac{\p\cdot n}2}$ )?

более точно именно так, сложность алгоритма $\sqrt{\frac{\p\cdot n}2}$ .
Если важен только порядок, то сложность $O(n^{\frac {1} {2}})$

yourdomain.com