Является ли сложность времени O (нм) равной O (n ^ 2), если m <= n

Question

Я изучаю временную сложность алгоритма, чтобы определить, содержит ли строка n подстроку m , где m <= n </em>. Результат анализа - временная сложность O (нм) . Итак, взяв эту временную сложность в качестве отправной точки и зная, что m <= n </em>, таким образом, mn <= n ^ 2 </em>. Можем ли мы сказать, что временная сложность в нотации большого O равна O (n ^ 2) .

Answer 1

Действительно, если время выполнения функции равно O (mn) и вы точно знаете, что m ≤ n, то время выполнения функции равно O (n ² ).

Однако, возможно, это не лучший способ охарактеризовать время выполнения. Если m - настраиваемый параметр, который может находиться в диапазоне, скажем, от 0 до n, то O (mn) может быть «лучшим» способом характеристики времени выполнения. Например, предположим, что это алгоритм, который находит m наименьших элементов из массива n элементов. Если вы хотите использовать этот алгоритм, чтобы найти пять верхних элементов (m = 5) из десяти миллионов (n = 10 ⁶ ), то характеризуя время выполнения как O (n ² ) значительно переоценил бы фактический объем проделанной работы, в то время как O (mn) дало бы лучшую оценку времени выполнения. хорошая причина характеризовать среду выполнения как O (mn), поскольку она показывает вам, как среда выполнения масштабируется со средой выполнения обеих входных строк, а не только одной из строк.

Надеюсь, это поможет!