Привет!
B программе для дипломной работы находится прямая по массиву заданых точек при помощи метода наименьших квадратов.
Формула для нахождения параметров линейной функции использует следующий компонент:
пол-дня, не могу понять, как найти сложность. Меня интересует верхняя граница, чаще всего для этого используется асимптотический анализ.
Помогите, кто знает
Спасибо
Помогите найти сложность алгоритма
Помогите найти сложность алгоритма
Последний раз редактировалось gaal 30 ноя 2019, 08:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Помогите найти сложность алгоритма
Что такое "сложность"? Тут можно десяток подходящих определений придумать.
Последний раз редактировалось qwertylol 30 ноя 2019, 08:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Помогите найти сложность алгоритма
qwertylol писал(а):Source of the post
Что такое "сложность"? Тут можно десяток подходящих определений придумать.
придумать я тоже многое могу, мне по существу ответ нужен.
Значит так: "сложность алгоритма" - выражение из теории алгоритмов, означает оценку времени выполнения программы. Чаще всего необходимо найти верхнюю границу при помощи асимптотического анализа, то есть при количестве входных данных стремящемся к бесконечности.
Никакие другие значения лично мне не известны.
Последний раз редактировалось gaal 30 ноя 2019, 08:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Помогите найти сложность алгоритма
gaal писал(а):Source of the post
придумать я тоже многое могу, мне по существу ответ нужен.
Значит так: "сложность алгоритма" - выражение из теории алгоритмов, означает оценку времени выполнения программы. Чаще всего необходимо найти верхнюю границу при помощи асимптотического анализа, то есть при количестве входных данных стремящемся к бесконечности.
Никакие другие значения лично мне не известны.
Это и есть по существу. См. Седжвика "Фундаментальные алгоритмы на C++", часть 1, глава 2. Привлекать математику тут совсем необязательно, достаточно проверить экспериментально и посмотреть к чему ближе.
Последний раз редактировалось qwertylol 30 ноя 2019, 08:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Помогите найти сложность алгоритма
qwertylol писал(а):Source of the postgaal писал(а):Source of the post
придумать я тоже многое могу, мне по существу ответ нужен.
Значит так: "сложность алгоритма" - выражение из теории алгоритмов, означает оценку времени выполнения программы. Чаще всего необходимо найти верхнюю границу при помощи асимптотического анализа, то есть при количестве входных данных стремящемся к бесконечности.
Никакие другие значения лично мне не известны.
Это и есть по существу. См. Седжвика "Фундаментальные алгоритмы на C++", часть 1, глава 2. Привлекать математику тут совсем необязательно, достаточно проверить экспериментально и посмотреть к чему ближе.
B том то и дело, что кроме результатов тестов нужно теоретическое обоснование, т.к. дипломная это.
Последний раз редактировалось gaal 30 ноя 2019, 08:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Помогите найти сложность алгоритма
gaal писал(а):Source of the post
Значит так: "сложность алгоритма" - выражение из теории алгоритмов, означает оценку времени выполнения программы. Чаще всего необходимо найти верхнюю границу при помощи асимптотического анализа, то есть при количестве входных данных стремящемся к бесконечности.
Никакие другие значения лично мне не известны.
Верхней границы значит не существует. Есть понятие линейной сложности. . Проверьте на линейность, может подойдет.
Последний раз редактировалось Таланов 30 ноя 2019, 08:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Помогите найти сложность алгоритма
Достаточно очевидно, по-моему, что трудоемкость алгоритма растет линейно c .
Последний раз редактировалось Pyotr 30 ноя 2019, 08:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Помогите найти сложность алгоритма
gaal писал(а):Source of the post
B том то и дело, что кроме результатов тестов нужно теоретическое обоснование, т.к. дипломная это.
Чтоб проводить асимптотику, нужно иметь функцию от времени. Тут можно посчитать только количество различных математических операций, если считать, что все они выполняются за одинаковое время и время больше ни на что не тратится, то получится 7n+5.
Последний раз редактировалось qwertylol 30 ноя 2019, 08:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Помогите найти сложность алгоритма
насколько я понимаю, нужно сначала просто подсчитать количеству умножений и сложений
Последний раз редактировалось Hottabych 30 ноя 2019, 08:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Помогите найти сложность алгоритма
Pyotr писал(а):Source of the post
Достаточно очевидно, по-моему, что трудоемкость алгоритма растет линейно c .
Спасибо за скорый ответ
He совсем понял, в силу чего очевидна линейная трудоемкость?:acute:
B знаменателе присутсвуют квадраты, кроме того в числителе перемножаются x и y под знаком суммы, или их суммы. Чисто интуитивно я бы сказал, что верхняя граница O(n^2).
Собственноо моя трудность в том, что я не знаю, как искать предел приведеной функции. Мне кажется, если разобраться c этим, то остальное - "дело техники".
Маленькое добавление: предел при n стремящемся к бесконечности.
Последний раз редактировалось gaal 30 ноя 2019, 08:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 52 гостей