Recuerda que en las ciencias informáticas un error suele tener más de una resoluciones, pero te compartiremos lo más óptimo y mejor.
Solución:
Tienes razón en que la distancia de r[i, j - 1] a r[i + 1, j] no es constante en el peor de los casos, pero es constante en promedio, lo que es suficiente para implicar un tiempo de ejecución cuadrático. El número total de iteraciones para l es
S = sum_i = 1^n - l + 1 (r[i + 1, j] + 1 - r[i, j - 1]), j = i + l - 1
= sum_i = 1^n - l + 1 (r[i + 1, i + l - 1] + 1 - r[i, i + l - 2])
= r[n - l + 2, n] + n - l + 1 - r[1, l - 1]
por tanto la media es S/(n – l + 1), que es una constante
simplificando la suma telescópica.
Puede encontrar el análisis de tiempo de ejecución exacto con una búsqueda en Google o simplemente comenzar a escribir su propio análisis para bucles. Pero solo tenga en cuenta que en todos ellos, la suma total se calcula mediante la suma telescópica, quiero decir, puede que uno de ellos sea grande, pero en cada iteración para el primer ciclo toma O (n), y toma totalmente O (n2).
Comentarios y calificaciones del post
Acuérdate de que te permitimos interpretar si te fue útil.