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

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

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

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

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

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

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

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

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