Обозначение Big O - Как вы описываете 2D-массив разной длины?

ProgramBox

Обозначение Big O — Как вы описываете 2D-массив разной длины?

Post author:admin
Запись опубликована:17 января, 2022
Post category:Вопросы по программированию

#algorithm #time-complexity #big-o

Вопрос:

У меня возникают проблемы с пониманием того, какой будет нотация Big O для вложенных структур данных, таких как 2D-массивы или объект массивов.

Сценарий

Суммируйте все значения во всех массивах.

Что я знаю

Например, я понимаю, что приведенная ниже структура данных будет O(n^2) такой, поскольку оба измерения имеют одинаковую длину (3×3).

 // O(n^2)

const arr = [
  [1,2,3],
  [1,2,3],
  [1,2,3],
]

Это будет O(n * m) где n длина первого измерения (2) и m длина второго измерения (3).

 // O(n * m)

const arr = [
  [1,2,3],
  [1,2,3],
]

Чего я не знаю

Но как насчет структуры данных, в которой массивы второго измерения имеют разную длину?

 // Maybe O(n * m)?

const arr = [
  [1,2,3],
  [1,2,3,4,5,6],
  [1,2]
]

let sum = 0

for (let nums of arr) {
  for (let num of nums) {
    arrSum  = num
  }
}

// sum = 30

Или объект, в котором значения являются массивами?

 // Maybe O(n * m)?

const obj = {
  a: [1,2,3],
  b: [1,2,3,4,5,6],
  c: [1,2]
}

let sum = 0

for (let nums of Object.values(obj)) {
  for (let num of nums) {
    sum  = num
  }
}

// sum = 30

Я в замешательстве от того, как это будет представлено в нотации Big O. Я думаю, что вы все равно будете O(n * m) указывать, где n длина первого измерения (или цифровых ключей), и m представляет собой самый длинный массив во втором измерении (или значение ключа).

Правильно ли я об этом думаю?

1. «m представляет самый длинный массив во втором измерении» звучит примерно правильно

2. » Я думаю, что вы все равно выбрали бы O(n * m), где n-длина первого измерения (или цифровых ключей), а m представляет самый длинный массив во втором измерении (или значение ключа). «кажется, правильно. Помните, что big-O не измеряет вещи конкретно, он предназначен для того, чтобы показать вам тенденцию роста.

Ответ №1:

Не нужно усложнять ситуацию больше, чем она есть на самом деле. n и m то и другое-просто переменные. То, что они описывают, полностью зависит от вас. На самом деле правильный выбор того, на чем вы основываете сложность выполнения вашего алгоритма, может иметь большое значение.

Таким образом, в случае массива массивов разной длины вы можете просто выбрать n в качестве суммы длину всех «внутренних» массивов. В случае с объектом проблема может быть сведена к первой проблеме. Незначительная придирка: вы зависите от внутреннего поведения Object.values ; Я просто предположил, что оно O(n) есть .

Итак, в общем: выберите наиболее точное описание проблемы-размер, а не структуру. Независимо от того, суммируете ли вы все элементы массива 256 x 256 или 2 x 32768 массива, это не будет иметь никакого значения с точки зрения сложности выполнения.

1. Это, безусловно, правильный способ думать об этом. Кстати, Object.values каждый раз возвращает новый массив, поэтому он не может быть быстрее линейного времени по количеству свойств. (Это не меняет временной сложности кода операции, потому что он вызывает только Object.values один раз, и это не доминирующий термин.)

2. @kaya3 ну, на самом деле это псевдокод, так что мы не можем знать наверняка. Если мы предполагаем Object.values , что работает на той же основе, что и реализация в javascript, вы правы. Но так как это псевдокод, к сожалению, можно только догадываться о внутренних компонентах без четкой спецификации. Определенно важное обсуждение, которое необходимо провести, чтобы правильно определить время выполнения

Ответ №2:

На самом деле, с точки зрения сложности, оба примера находятся внутри O(n * m) . Но иногда вам требуется более жесткая временная сложность. В вашем случае, если мы предположим , что длина массивов равна m_1, m_2, ..., m_n , вы можете указать идентификатор временной сложности Theta(sum_{i = 1}^{n} m_i) . В этом случае вы можете упростить его, исходя из существующих ситуаций. Например, иногда сумма длин равна постоянному коэффициенту n , например, 2n . В этом случае временная сложность будет O(2n) .

Метки: Обозначение Big O — Как вы описываете 2D-массив разной длины?