Как вычислить точную сложность алгоритма?

Question

Не прибегая к асимптотическим обозначениям, является ли утомительный подсчет шагов единственным способом получить временную сложность алгоритма?И без подсчета шагов для каждой строки кода мы можем прийти к представлению big-O любой программы?

Подробности: пытаясь выяснить сложность нескольких алгоритмов численного анализа, чтобы решить, какой из них лучше всего подходит для решенияконкретная проблема.Например, из числа методов Регула-Фальси или Ньютона-Рапсона для решения уравнений предполагается оценить точную сложность каждого метода, а затем решить (указав значение n или любые другие аргументы), какой метод является менее сложным.

Answer 1

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

Но, если вы действительно хотите посчитать шаги автоматически, есть и способы сделать это.Вы можете добавить команду приращения счетчика (например, «bloof ++;» в C) к каждой строке кода, а затем отобразить значение в конце.

Вы также должны знать о более усовершенствованном выражении сложности времени, f(n) * (1 + o (1)), что также полезно для аналитических расчетов.Например, n ^ 2 + 2 * n + 7 упрощается до n ^ 2 * (1 + o (1)).Если постоянный фактор - это то, что беспокоит вас в обычной асимптотической записи O (f (n)), это уточнение является способом отследить его и все равно выбросить незначительные члены.

Answer 2

«Простой способ» - смоделировать его. Попробуйте свои алгоритмы с множеством значений n и множеством различных данных, нанесите результаты и сопоставьте кривую на графике с уравнением.

Ваши результаты могут быть не совсем точными, и они действительны настолько же, насколько и ваша способность генерировать хорошие тестовые данные, но в большинстве случаев это будет работать.

Answer 3

например. - из числа методов Регула-Фальси или Ньютона-Рапсона для решения уравнений предполагается оценить точную сложность каждого метода и затем решить (указав значение n или любые другие аргументы), какой метод является менее сложным.

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

Подводя итог, наиболее эффективный нелинейный решатель всегда зависит от проблемы, которую вы решаете. Если разнообразие проблем, которые вы решаете, очень ограничено, проведение ряда экспериментов с различными решателями и измерение количества итераций и времени процессора, вероятно, даст вам более полезную информацию.