алгоритмической сложности 2D матрицы

Question

Если у меня есть 2D массив, то в каких условиях будет рассчитана алгоритмическая сложность, с точки зрения порядка или с точки зрения нет элементов

Answer 1

Насколько я знаю, есть два общая нотация -

1. n * m где каждая переменная обозначает измерение. В этом случае, если человек пренебрежимо мал по отношению к другому, вы можете рассматривать его как константу.

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

Answer 2

Нет общепринятого единственного способа сделать это.

• Если это квадратная матрица, мы можем просто использовать число строк (или столбцов) n.

• Мы можем использовать количество строк r и количество столбцов c.

• Мы можем использовать количество ячеек n.

Названия переменных, используемые выше, несколько произвольны.

Я целенаправленно использовал n как для количества строк, так и для количества ячеек, как обычно можно использовать на практике (поскольку n - это имя переменной, обычно используемое для «входного размера», но мы его определяем).

Так, например, если у нас есть алгоритм линейного времени (т.е. проверять каждую клетку один раз), мы имеем:

• O(n2)

• O(r*c)

• O(n)

соответственно для вышеуказанного.