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

Question

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

• ... урожаи много результатов? В общем случае (тогда алгоритм, производящий набор k, не может быть быстрее, чем O (k)) или за элемент (тогда оценка должна быть умножена для сравнения с алгоритмами, не создаваемыми для создания)?
  • Как насчет сложности хранилища - отражается ли оценка, должен ли весь набор присутствовать в памяти сразу или каждый последующий элемент может быть создан и отброшен?
• ... имеет несколько параметров? Отдельная цифра для каждого параметра или что-то вместе?

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

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

_{Вопросы, которые имели меня озадачило об этом являются: Unique (non-repeating) random numbers in O(1)?, How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N, Algorithm to select a single, random combination of values?, Efficiently selecting a set of random elements from a linked list.}

Answer 1

Согласно the answer at CS.SE:

• времени сложность и пространство сложности должны быть представлены отдельно и отдельно для каждой переменной: "О (к) и О (п) время, O (1) пространство ".
  • Если время/пространство не зависит от некоторых переменных, но не все, что может быть сказано в виде простого текста или что-то вроде O (п) для краткости (нет универсальной конвенции здесь)
• все результаты возвращаются ли в конце или один за другим отражается refferring алгоритму, как потоковое (онлайн) (по одному) или партии (все в конце)
  • Для алгоритма потоковой передачи, его задержка также может быть описана:

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

Answer 2

Этим вопросам обычно отвечает контекст.

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

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