Какова общая O (n) временная сложность O (sum (a)), если a - массив целых чисел, а n - длина массива? - PullRequest
Новая
       5

Какова общая O (n) временная сложность O (sum (a)), если a - массив целых чисел, а n - длина массива?

0 голосов
/ 26 мая 2018

Мне трудно использовать принципы O (n), чтобы обобщить временную сложность алгоритма, более специфическая временная сложность которого равна O (sum (a)), где a - массив целых чисел.

Моя интуиция заключается в том, что эта временная сложность должна быть обобщена до O (n), поскольку вы можете думать об этом как о «линейном» уравнении значений ki, которые встречаются n раз, где k - целочисленное значение в массиве, что делает его O (n)(k = 1 для случая прямого O (n)).

Но, похоже, это не то же самое, что O (n) - значение k может быть намного больше, чем n, иесли все эти значения k больше, у вас есть что-то, что может быть O (n ^ 2) или O (n ^ 3) в зависимости от того, насколько велико это значение.

Должно ли это учитываться для сложности O (n), где n - длина массива?Должен ли я на самом деле определять n как сумму всех элементов в массиве, а не длину массива?

В общем, что будет лучшим способом думать об этом?

1 Ответ

0 голосов
/ 26 мая 2018

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

Существует два варианта (или упрощения), которые часто делают при расчете времени выполнения.Во-первых, игнорировать фактический вход и использовать вместо него размер входа (измеренный каким-либо образом).Этот размер обычно обозначается n.Во-вторых, использовать нотацию big-O для описания наихудшего случая (или лучшего, или среднего, или амортизированного ...).

Ни один из этих вариантов не всегда необходим, и иногда они выигрывают 'не имеет смысла.Повторим, так как это суть ответа: описание времени выполнения в big-O n - не единственный способ описания времени выполнения, и иногда нет смысла это делать.

Например, вслучай алгоритма, который выполняется за O(sum(a)) время: 

func f(a) {
   t = 0
   for x in a {
      for i = 1..x {
         t += 1
      }
   }
}

Бесполезно описывать время выполнения этого с использованием длины входного массива a.Это бесполезно, потому что длина a ничего не говорит о времени выполнения в худшем случае.

Сказать, что t увеличивается sum(a) раз , это полезное утверждение овремя выполнения программы.Он не использует нотацию сложности big-O.

И если вы do хотите выразить это в нотации big-O, вы можете сказать, что время выполнения этого кода равно O(sum(a)),Это размывает в точности то, что вы измеряете во время выполнения, потому что вы можете включить стоимость выполнения операторов, кроме увеличения t.

. Возвращаясь к примеру, вы могли бы (и если вы изучаете классы сложности, вы, вероятно, ) скажете, n - это размер (в битах) входного массива.Тогда вы могли бы что-то сказать о времени выполнения (измеряется в основных операциях): это O (2 ^ n), поскольку наихудшим случаем ввода является массив с одним элементом, который принимает значение 2 ^ n-1 (* note).

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

...