Вычислительная сложность для случая многих ответов или нескольких параметров

Как определяется вычислительная сложность, если алгоритм:

  • ...yields many results? As a total (then an algorithm producing a set of k cannot be faster than O(k) ) or per element (then the estimate must be multiplied to compare it with non-set-producing algorithms)?
    • What about storage complexity - does an estimate reflect if the entire set needs to be present in memory at once or each consecutive element can be produced and discarded?
  • ...имеет несколько параметров? Отдельный показатель для каждого параметра или что-то комбинированное?

Примером, подходящим для обоих случаев, является выбор k элементов из N. Например. есть ли разница в оценке в зависимости от того, требуется ли ~k или ~N шагов?

Я хотел бы увидеть веские доказательства: формальное определение термина в этих случаях и/или то, как эта двусмысленность устраняется в документах по компьютерным наукам, а не просто случайные мысли и/или личный опыт. Цель состоит в том, чтобы выработать полное, современное решение, чтобы раз и навсегда устранить эти двусмысленности в моих (и чужих) текстах.

Меня озадачили следующие вопросы: Уникальные (неповторяющиеся) случайные числа в O(1)?, Как эффективно сгенерировать список из K неповторяющихся целых чисел от 0 до верхней границы N, Алгоритм выбора одной случайной комбинации значений?, Эффективный выбор набора случайных элементов из связанного списка.


algorithm complexity-theory computer-science-theory
person ivan_pozdeev    schedule 09.09.2016    source источник
comment
Для вопроса о нескольких параметрах см. раздел параметризованная сложность или управляемость с фиксированными параметрами.   -  person sascha    schedule 10.09.2016
comment
Не получив никаких входных данных желаемого качества, я теперь задал часть формального метода на cs.se, так как формальные вещи там более актуальны.   -  person ivan_pozdeev    schedule 17.11.2016

Ответы (2)


arrow_upward
1
arrow_downward

Обычно на эти вопросы отвечает контекст.

Вы правы в том, что алгоритму требуется не менее O(k) времени при возврате k элементов. По крайней мере, если он возвращает элементы сразу. Если алгоритм вызывается несколько раз для получения результата по одному элементу за раз, заявленная временная сложность может относиться к времени для каждого элемента. В таких случаях может помочь Амортизированная сложность. Например, структура данных union-find имеет амортизированную временную сложность O(alpha( п)) за операцию. Объемная сложность обычно не включает место для хранения результата. Но опять же, это должно быть ясно из контекста.

Для нескольких параметров (или других независимых или зависимых переменных) сложности обычно указываются в одном выражении. Например, запрос интервальных деревьев требует O(n + m) времени, где n — количество элементов. в дереве, а m — количество возвращаемых элементов. Другие переменные могут включать распределение данных или другие характеристики.

person Nico Schertler    schedule 09.09.2016
comment
Итак, на вопрос, как определяется CC, вы в основном говорите, что нет определения? - person ivan_pozdeev; 10.09.2016
comment
Нет, есть определение, конечно. Нужно только уточнить, какую сложность вы заявляете. Как уже упоминалось, есть несколько вариантов. И иногда люди не очень осторожны с терминологией. Так что я бы не стал полагаться на некоторые вопросы, чтобы запутаться. - person Nico Schertler; 10.09.2016
comment
Хорошо, перефразируя: не существует официального согласованного определения. Из разряда, пригодного для научных работ, то есть. И вы говорите Вам просто нужно уточнить, какую сложность вы указываете. но не говорите, какие сложности существуют, т.е. какие обычно используются . Как видно из связанных вопросов, это неясно из контекста, что противоречит вашему утверждению. - person ivan_pozdeev; 11.09.2016
comment
Это очень специфично для алгоритма. Если ваш алгоритм состоит из одной функции, которую вы вызываете один раз, это вполне понятно. Если алгоритм или структура данных поддерживает несколько вызовов функций, вы можете рассмотреть амортизированную временную сложность. В любом случае вы должны указать это в виде: время генерации одного случайного числа равно ..., время генерации x k раз равно ... и так далее. Если вы это сделаете, он будет пуленепробиваемым. Какой из связанных вопросов смущает вас? - person Nico Schertler; 11.09.2016
comment
stackoverflow.com/questions/196017 - O (1) недостижимо - как я могу говорить о сложности с этим в заголовке? ; stackoverflow.com/questions/158716 — некоторые алгоритмы требуют ~k шагов, а другие — ~N; одним нужен массив из k, другим - из N; некоторые даже способны выдавать элементы один за другим (будут ли они накапливаться во внутреннем массиве и возвращаться вместе в конце, является деталью реализации). Было бы очень хорошо, если бы вы продемонстрировали свои рассуждения на примерах (например, возьмите хорошие ответы — те, которые ссылаются на документы CS). - person ivan_pozdeev; 11.09.2016
comment
С первым действительно не очень понятно. Но поскольку сгенерировать список за O(1) невозможно, автор должен иметь в виду временную сложность генерации следующего элемента. Для второго - проблема с генерацией списка (а не только одного элемента). Итак, если алгоритм требует количества шагов, пропорционального k``, then it is O(k). If the number of steps is proportional to n, then it is O(n)`. - person Nico Schertler; 11.09.2016

arrow_upward
0
arrow_downward

Согласно ответ на CS.SE:

  • Time complexity and space complexity shall be reported separately and separately for each variable: "O(k) and O(n) time, O(1) space".
    • If the time/space doesn't depend on some of the variables but not all, this can be told in plain text or with something like O(n0) for brevity (there's no universal convention here)
  • Whether all the results are returned at the end or one by one is reflected by refferring to the algorithm as streaming (online) (one by one) or batch (all at the end)
    • For a streaming algorithm, its delay can also be described:

      Например, алгоритм задержки O(log n) возвращает результаты по одному, выполняя не более O(log n) шагов (время выполнения) для вывода каждого результата.

person ivan_pozdeev    schedule 20.01.2017