Временная сложность для l oop, где я начинаю с переменной (не 1 или 0)

Question

Я хочу знать временную сложность a для l oop для (i = m; i <= n; i ++), где m и n обе переменные. Я думаю, что это будет O (нм), так как l oop зависит как от значений m и n. Пожалуйста, ведите меня! </p>

Answer 1

Объяснение

Предполагая, что ваш l oop выполняет только операторы, которые выполняются в постоянное время, т.е. O(1), вам просто нужно посчитать количество итераций l oop.

Ваша голова l oop

 for (i = m; i <= n; i++)

будет генерировать итерации с i, равным m, m + 1, m + 2, m + 3, ..., n - 2, n - 1 n. Таким образом, от m до n, оба конца включительно.

То есть ровно n - m + 1 итераций (простой пример 2, 3, 4, 5 с 5 - 2 + 1 = 4).

Таким образом, асимптотика c сложность времени равна

O(n - m + 1) = O(n - m)

Как вы сказали.

Answer 2

Да, действительно, это O(n-m+1), поскольку оно начинается с m и достигает n в худшем случае.