Меня давно мучает вопрос- как дают оценки алгоритмам?
Для примера возьмём пузырьковую сортировку(что может быть проще?). Вот c чего они взяли, что сложность именно (в сети легко найти и более точные оценки)? Обычно оценивают суммы или интегралы, a тут алгоритмы...
Оценка алгоритмов
Оценка алгоритмов
Последний раз редактировалось qwertylol 30 ноя 2019, 10:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Оценка алгоритмов
Обычно оценивают порядок числа арифметических действий при реализации алгоритма c заданной точностью.
Последний раз редактировалось venja 30 ноя 2019, 10:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Оценка алгоритмов
venja писал(а):Source of the post
Обычно оценивают порядок числа арифметических действий при реализации алгоритма c заданной точностью.
Ну тогда в этом примере сложность нуль . Тут ведь арифметики нет :no: .
Последний раз редактировалось qwertylol 30 ноя 2019, 10:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Оценка алгоритмов
Скажем в пузыре максимум может быть сравнений(как раз ) и столько же обменов. Ho в той же сортировке выбором сложность указана такая же, хотя обменов там ровно .
Последний раз редактировалось qwertylol 30 ноя 2019, 10:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Оценка алгоритмов
qwertylol писал(а):Source of the post
Ho в той же сортировке выбором сложность указана такая же, хотя обменов там ровно .
B сортировке выбором сравнений , обменов , поэтому общая сложность алгоритма
Последний раз редактировалось krsnv 30 ноя 2019, 10:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Оценка алгоритмов
Странно, что это за алгоритм совсем без арифметики? Впрочем вместо арифметики могут быть другие действия, к примеру булевы. B пузырьковых камерах я совсем не разбираюсь, возьму другой пример. Требуется сравнить сложность нахождения решения крамеровской систему по двум алгоритмам:
1) по формуле Крамера
2) методом гауссовых исключений
B первом случае число действий прикидываем опять же по алгоритму вычисления определителя методом гауссовых вычислений.
За единицу сложности примем элементарную операцию выполняемую над числами и при любом фиксированном .
При нахождении одного определителя приводим его к треугольному виду - это потребует действий над мерными массивами плюс действий над мерными массивами плюс ...
Итого получаем элементарных действий.
Всего надо сосчитать определителей, стало быть сложность
По второму алгоритму треугольного вида мало - надо сделать прямой ход и обратный ход над мерными массивами. на асимтотику не влияет, a упрощением обратного хода из-за появления нижних нулей пренебрежём и отнесём в пользу бедных - первого алгоритма. Итого сложность второго алгоритма
C переходом к O большим множитель отбрасывается и получаем соответственно и , то есть при достаточно больших второй алгоритм лучше.
Ha практике так и есть - при как правило лучше по Крамеру, при вопрос довольно спорный, так как конкретность чисел может внести значительные коррективы в оценку, a вот при уже трудно будет привести пример, где по Крамеру легче.
1) по формуле Крамера
2) методом гауссовых исключений
B первом случае число действий прикидываем опять же по алгоритму вычисления определителя методом гауссовых вычислений.
За единицу сложности примем элементарную операцию выполняемую над числами и при любом фиксированном .
При нахождении одного определителя приводим его к треугольному виду - это потребует действий над мерными массивами плюс действий над мерными массивами плюс ...
Итого получаем элементарных действий.
Всего надо сосчитать определителей, стало быть сложность
По второму алгоритму треугольного вида мало - надо сделать прямой ход и обратный ход над мерными массивами. на асимтотику не влияет, a упрощением обратного хода из-за появления нижних нулей пренебрежём и отнесём в пользу бедных - первого алгоритма. Итого сложность второго алгоритма
C переходом к O большим множитель отбрасывается и получаем соответственно и , то есть при достаточно больших второй алгоритм лучше.
Ha практике так и есть - при как правило лучше по Крамеру, при вопрос довольно спорный, так как конкретность чисел может внести значительные коррективы в оценку, a вот при уже трудно будет привести пример, где по Крамеру легче.
Последний раз редактировалось bot 30 ноя 2019, 10:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Оценка алгоритмов
bot, большое спасибо за объяснение, но здесь видите в чём проблема- непонятно, что берут за "единицу сложности". Вот цитата из книги "Конкретная математика. Основание информатики":
A на описание метода пузырька я оставлял ссылку в первом посте и к пузырьковым камерам он отношения не имеет . Это простейший алгоритм сортировки и умещается он в пару строк(потому я его и выбрал).
[url=http://ru.wikipedia.org/wiki/Сортировка_пузырьком]http://ru.wikipedia.org/wiki/Сортир\xD0...\x83зырьком[/url]
Ну допустим всё так, тогда каким образом мне оценить алгоритм более точно()?
Откуда эта сумма взялась авторы, увы, умолчали .Среднее время алгоритма, называемого "сортировка методом пузырька" зависит от асимптотического значения суммы .
A на описание метода пузырька я оставлял ссылку в первом посте и к пузырьковым камерам он отношения не имеет . Это простейший алгоритм сортировки и умещается он в пару строк(потому я его и выбрал).
[url=http://ru.wikipedia.org/wiki/Сортировка_пузырьком]http://ru.wikipedia.org/wiki/Сортир\xD0...\x83зырьком[/url]
B сортировке выбором сравнений , обменов , поэтому общая сложность алгоритма
Ну допустим всё так, тогда каким образом мне оценить алгоритм более точно()?
Последний раз редактировалось qwertylol 30 ноя 2019, 10:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Оценка алгоритмов
что берут за "единицу сложности"?
Часто в статьях приходилось видеть отдельную оценку сложностей алгоритма по разным операциям, например:
- операций сравнения
- операций сложения
Последний раз редактировалось krsnv 30 ноя 2019, 10:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Оценка алгоритмов
krsnv писал(а):Source of the post
Часто в статьях приходилось видеть отдельную оценку сложностей алгоритма по разным операциям, например:
- операций сравнения
- операций сложения
Меня интересует именно время выполнения алгоритма и везде имелось ввиду именно это.
Последний раз редактировалось qwertylol 30 ноя 2019, 10:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Оценка алгоритмов
тогда каким образом мне оценить алгоритм более точно()?
более точно именно так, сложность алгоритма .
Если важен только порядок, то сложность
Последний раз редактировалось krsnv 30 ноя 2019, 10:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 2 гостей