Наихудший случай сложности Big (O) для ввода 2 переменных

Question

Я реализовал алгоритм, который принимает на вход матрицу из R строк и C столбцов. Я говорю, что наихудшая временная сложность алгоритма равна O(C√C * R^3) или O(C^1.5 * R^3)

Теперь кто-то спрашивает меня, нельзя ли это обозначить просто O(R^3) для наихудшего случая. Я бы сказал, что, поскольку есть 2 входа (а не один), и иногда C может быть большим, а иногда R может быть большим, поэтому мы не можем уменьшить его до O(R^3), и следует учитывать как C, так и R. .

Правильный ли мой ответ? Если нет, то почему?

Answer 1

Да, вы правы, вы не можете просто игнорировать любой из входных параметров, учитывая временную сложность.

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

В вашем случае, как уже упоминалось, временная сложность должна быть указана как O(C^1.5 * R^3)

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

Например. Если ввод: R - любое число C - любое число> = R

В приведенном выше случае

O(R*C) = O(R*C) -> Мы не можем просто игнорировать любой входной параметр

O(R+C) = O(C) -> Как мы знаем, C всегда будет больше, чем R

Answer 2

Вы правы, что C и R. должны учитываться в вашем выражении Big O.

Анализ Big O полезен в ситуациях, когда размер вашего ввода может отличаться, и здесь размер ваш ввод требует двух параметров для описания, поскольку вы говорите, что «иногда C может быть большим, а иногда R может быть большим».

Единственный способ устранить C - это если бы C было O (1), и в этом случае ваша функция будет расти как O (R ^ 3), или если C будет функцией R, например, если C = O (R), ваша функция будет расти как O (R ^ 4.5).