Оценка алгоритма в котором кол-во итераций не задано явно (С++)

Берём конкретную задачу из книжки:
y'' = y'²/y + y/x, y(0)=1, y(1)=1. Она подходит как тестовый пример для жёстких систем, поскольку видно, что в точке x=0 функция жёсткая. Многие обычные методы при интегрировании таких нелиненых систем с жёсткими элементами часто дают сбой, а самые медленные и неуклюжие алгоритмы, но обладающие регуляризующими свойствами, являются очень надёжными. Выберем для решения этой задачи метод усреднения. Этот итерационный метод медленный, конечно, да ещё и точность его порядка O(1/n), что тоже не очень хорошо, но зато он регулярный. Ищем узловые решения на равномерной сетке с n интервалами, заменяя производные их центральными разностями. Количество итераций заранее неизвестно. Итерирование прекращается тогда, когда вектор узловых решений перестаёт улучшаться.
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
using namespace std;
double f(double x, double y, double z)
{ return y / x + z * z / y; }
int main()
{
int i, j, n, np, t;
double a, ya, b, yb, c, x, h,
hh, e, emax, E, u, v, *y, *yi, d;
for (;;)
{
cout << "a y(a) b y(b) n >> ";
cin >> a >> ya >> b >> yb >> n;
t = time(nullptr);
np = n + 1;
c = (yb - ya) / n;
E = 1e303;
h = (b - a) / n;
hh = h * h;
d = 0.5 / h;
y = new double[np];
yi = new double[np];
for (j = 0; j <= n; j++)
y[j] = yi[j] = ya + c * j;
for (i = 1;; i++)
{
emax = 0;
for (j = 1; j < n; j++)
{
u = yi[j - 1];
v = y[j + 1];
x = a + j * h;
yi[j] = (u + v - hh * f(x, y[j], (v - u) * d)) * 0.5;
e = abs(yi[j] - y[j]);
if (e > emax) emax = e;
}
if (emax >= E) break;
else
{
E = emax;
for (j = 1; j < n; j++) y[j] = yi[j];
}
}
cout << i << ' ' << E << endl;
for (j = 0; j <= n; j++)
{
x = a + j * h;
printf("%10.4f%22.16f%16.6e\n",
x, y[j], y[j] - pow(x, x));
}
delete[] y;
delete[] yi;
cout << "time = " << time(nullptr) - t
<< " seconds" << endl;
}
}
Запускаем задачу прямо на телефоне или планшете, вводя краевые условия и значения n. Вот какие получаются промежутки времени для решения этой задачи:
500 >> 18'' (358222 итерации)
1000 >> 115'' (1140959 итераций)
2000 >> 693'' (3443672 итерации)
В конце оцениваем временнУю сложность алгоритма. Оценки получаются несколько расплывчатыми, но в целом эмпирическая оценка где-то O(n^2,58..2,68).
А вот пример из несколько иной области (из проекта "Эйлер"). Надо найти количество простейших героновых треугольников с гипотенузой, не превышающей N, а потом временнУю сложность алгоритма, выбранного для решения этой задачи. Простейшие героновы тройки -это тройки взаимопростых целых чисел, для которых площадь треугольника -тоже целое число. Тут эмпирическая сложность получается около O(N³):
#include <iostream>
#include <iomanip>
#include <cmath>
#include <ctime>
using namespace std; int e(int x,int y)
{ int z; while (true) { z=x%y; if (z==0)
return y; x=y; y=z; } }
int main() { struct triangle { double s; int a,b,
c; }; triangle T[100000]; int a,ab,b,c,l,m,n,t;
double p,s; cout.precision(17); for (;;) { cout <<
"n = ?\b"; cin >> n; t=time(0); m=0; for (a=1;
a<=n; a++) for (b=a; b<=n; b++) { l=n+1; ab=a+b;
if(ab<l) l=ab; for (c=b; c<l; c++) { p=(a+b+c)*0.5;
s=sqrt(p*(p-a)*(p-b)*(p-c)); if (round(s)==s) if
(e(e(a,b),c)==1) { T[m].s=s; T[m].a=a; T[m].b=b;
T[m].c=c; m++; } } } cout << m << ' ' << time(0) - t
<< endl; } }
N=500: 6093 треугольника, 5..6''
1500: 10984, 19''
2000: 16719, 44''
3000: 30165, 149''

Явно кол-во итераций практически никогда не известно. Вот задача: есть массив без ограничений, надо найти в нем элемент Х. Сложность - O(N), банальный перебор. Однако в конкретном случае это может быть как 1 итерация (Х на 0м месте), так и N итераций (Х - последний или отсутствует), так и любое число из промежутка [1-N].

Поэтому включаем мат статистику, вспоминаем нормальное распределение и метод минимакса. Поскольку поиск никогда не займет больше N итераций, а скорость роста O(N) и O(N/2) отличаются на константу, адекватной оценкой является именно O(N)

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

Если количество итераций не задано, то имеется в виду не линейная, а какая-либо иная сложность алгоритма, в которой скорость или сложность вычислений никак не зависит от объёма входящих данных.
Например, алгоритм нахождения значения конкретного элемента в массиве, допустим, нужно просто найти значение 3-го элемента в векторе. При этом объем входящих данных не важен, и все значения элементов перебирать не нужно. В таком алгоритме сложность обозначается просто как O(1). Время работы такого алгоритма вообще не зависит от объема входящих данных.

Вводная лекция Кнута по сложности алгоритмов, где он рассматривает в частности, как считать количество шагов для каждой точки: https://www.youtube.com/watch?v=sTFTCfrMWkk