Я хотел бы сравнить различные методы поиска корней функций в python (например, методы Ньютона или другие простые методы, основанные на расчетах). Я не думаю, что у меня возникнут большие проблемы с написанием алгоритмов.
Что было бы хорошим способом сделать фактическое сравнение? Я немного почитал о Big-O. Будет ли это путь?
Ответ от @sarnold правильный - нет смысла проводить анализ Big-Oh.
Принципиальные различия между алгоритмами поиска корней заключаются в следующем:
Я думаю, вы обнаружите, что у каждого из методов есть хорошие качества, некоторые плохие качества и набор ситуаций, в которых он является наиболее подходящим выбором.
Большая нотация O идеально подходит для выражения асимптотического поведения алгоритмов по мере "увеличения" входных данных для алгоритмов. . Вероятно, это не очень хорошая мера для алгоритмов поиска корней.
Вместо этого я бы подумал, что количество итераций, необходимых для снижения фактической ошибки ниже некоторого эпсилон ε, было бы лучшей мерой. Другой мерой может быть количество итераций, необходимых для уменьшения разницы между последовательными итерациями ниже некоторого эпсилон ε. (Разница между последовательными итерациями, вероятно, является лучшим выбором, если у вас нет под рукой точных корневых значений для ваших входных данных. Вы должны использовать критерий, такой как последовательные различия, чтобы знать, когда на практике прекращать поиск корней, чтобы вы могли или следует использовать их и здесь.)
Хотя вы можете охарактеризовать количество итераций, необходимых для различных алгоритмов, с помощью соотношений между ними (один алгоритм может потребовать примерно в десять раз больше итераций, чтобы достичь той же точности, что и другой), часто не происходит "роста". " в итерациях по мере изменения входных данных.
Конечно, если ваши алгоритмы выполняют больше итераций с «большими» входными данными, тогда запись Big O имеет смысл.
Нотация Big-O предназначена для описания того, как алгоритм ведет себя в пределе, когда n стремится к бесконечности. С этим гораздо легче работать в теоретическом исследовании, чем в практическом эксперименте. Я бы выбрал для изучения вещи, которые можно легко измерить и которые волнуют людей, например, точность и потребляемые компьютерные ресурсы (время/память).
Когда вы пишете и запускаете компьютерную программу для сравнения двух алгоритмов, вы проводите научный эксперимент, точно так же, как кто-то, кто измеряет скорость света, или кто-то, кто сравнивает уровень смертности курильщиков и некурящих, и многие из тех же факторов применять.
Попробуйте выбрать пример проблемы или проблем, которые необходимо решить, которые являются репрезентативными или, по крайней мере, интересными для вас, потому что ваши результаты могут не распространяться на ситуации, которые вы на самом деле не тестировали. Вы можете увеличить диапазон ситуаций, на которые отвечают ваши результаты, если вы выберете наугад из большого набора возможных проблем и обнаружите, что все ваши случайные выборки ведут себя во многом одинаково или, по крайней мере, следуют одной и той же тенденции. Вы можете получить неожиданные результаты, даже если теоретические исследования показывают, что должна быть хорошая тенденция n log n, потому что теоретические исследования редко учитывают внезапное исчерпание кеша или нехватки памяти или, как правило, даже такие вещи, как целочисленное переполнение.
Будьте внимательны к источникам ошибок и постарайтесь свести их к минимуму или сделать так, чтобы они применялись в одинаковой степени ко всем вещам, которые вы сравниваете. Конечно, вы хотите использовать одни и те же входные данные для всех тестируемых алгоритмов. Сделайте несколько прогонов каждого алгоритма и проверьте, насколько изменчивы вещи — возможно, несколько прогонов медленнее, потому что компьютер в это время делал что-то еще. Имейте в виду, что кэширование может ускорить более поздние запуски алгоритма, особенно если вы запускаете их сразу друг за другом. Какое время вы хотите, зависит от того, что вы решили измерять. Если у вас много операций ввода-вывода, помните, что современные операционные системы и компьютеры кэшируют в памяти огромные объемы дисковых операций ввода-вывода. Однажды я закончил тем, что выключал и снова включал компьютер после каждого запуска, поскольку это был единственный способ убедиться, что кэш ввода-вывода устройства очищен.
Вы можете получить совершенно разные ответы на одну и ту же проблему, просто изменив исходные точки. Выберите начальное предположение, близкое к корню, и метод Ньютона даст вам результат, сходящийся квадратично. Выберите другую в другой части проблемного пространства, и поиск корней сильно разойдется.
Что это говорит об алгоритме? Хорошо или плохо?
Я бы посоветовал вам взглянуть на следующую демонстрацию поиска корня Python. Это простой код с некоторыми различными методами и сравнениями между ними (с точки зрения скорости сходимости).
http://www.math-cs.gordon.edu/courses/mat342/python/findroot.py
Я только что закончил проект, в котором сравниваются методы поиска корня пополам, Ньютона и секущего. Поскольку это практический случай, я не думаю, что вам нужно использовать нотацию Big-O. Обозначение Big-O больше подходит для асимптотического представления. Что вы можете сделать, так это сравнить их с точки зрения:
Скорость - например здесь ньютон самый быстрый, если собрано хорошее состояние
Количество итераций - например, здесь деление пополам занимает наибольшее количество итераций
Точность — как часто он сходится к правому корню, если корней больше одного, или, может быть, он даже не сходится вообще.
Входные данные — какая информация нужна для начала работы. например, Ньютону нужно X0 около корня, чтобы сходиться, ему также нужна первая производная, которую не всегда легко найти.
Другое - ошибки округления
Для визуализации вы можете хранить значение каждой итерации в массивах и отображать их. Используйте функцию, корни которой вы уже знаете.
Хотя это очень старый пост, мои 2 цента :)
Как только вы решили, какой алгоритмический метод использовать для их сравнения (так сказать, ваш «протокол оценки»), вас могут заинтересовать способы запуска ваших претендентов на реальных наборах данных.
В этом руководстве объясняется, как это сделать, на примере (сравнение полиномиальных алгоритмы подбора на нескольких наборах данных).
(Я автор, не стесняйтесь оставлять отзывы на странице github!)
