Вычисление сложности алгоритма с использованием Big O

Question

Я пытаюсь вычислить сложность различных вариантов алгоритма с использованием Big O.

Упрощенное описание алгоритма следующим образом:

Давайте рассмотрим «преобразователь» функция который принимает определенный объект и преобразует его в другое представление. Каждый конвертер определяет свой домен и диапазон.

Существует процедура, которая принимает объект-источник (то есть объект для преобразования), список функций преобразователя и ожидаемый тип преобразования.

Он выполняет итерацию в списке преобразователей, пока не найдет конвертер, домен и диапазон которого совместимы с объектом для преобразования и ожидаемым типом преобразования.

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

Теперь, какая будет сложность, если каждому конвертеру может потребоваться рекурсивно вызывать процедуру преобразования определенное количество раз?

Например, может потребоваться преобразование определенных компонентов исходного объекта в другие объекты, которые впоследствии будут собраны в качестве возвращаемого объекта (цель первоначального преобразования).

Как я понимаю, неформально это дает:

n + m1(n + m2 (n + m3 (...)))) 

Где:

• п является мерой усилия, чтобы найти оригинальный конвертер.
• m1 количество подкомпонентов исходного объекта, которые должны быть преобразованы в процедуру преобразования.
• m2 максимальное количество подкомпонентов от исходных объектов m1.
• и т.д ...

В качестве дополнительных деталей, количество подкомпонентов для преобразования должно уменьшаться на каждом рекурсивном вызове.

Это правильно? Если да, то как мне уменьшить эту формулу до нотации Big O?

И, наконец, какая будет сложность, если есть какая-то интеллектуальная система индексирования, которая позволяет мне быстро найти правильную функцию конвертера в списке преобразователей? Насколько я понимаю, в простейшем случае, когда конвертер не вызывает функцию преобразования рекурсивно, это должно быть O (log n), правильно?.

Но какова будет сложность алгоритма на основе индексирования, если каждый конвертер, как и в предыдущем случае, может потребоваться рекурсивно вызвать функцию преобразования?

Answer 1

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

Не обязательно. Асимптотическая сложность связана с размером вашего ввода (в байтах).Если ваш объект имеет постоянный размер, то общий размер ввода (ваш N) будет асимптотически пропорционален числу конвертеров, поэтому итерация по ним будет равна O (N). С другой стороны, если ваш объект большой - скажем, матрица m m, где m - количество преобразователей, то ваш N будет пропорционален m^2, и итерация будет O (m), что это только O (sqrt (n)). Другим важным случаем является то, что количество преобразователей ограничено константой, а не тем, что вызывающий может устанавливать так высоко, как он хочет - в случае, если итерация равна O (1).

Теперь, какая была бы сложность, если каждому конвертеру может потребоваться рекурсивно вызывать процедуру преобразования определенное количество раз?

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

Как я понимаю, это дает

n + m1(n + m2 (n + m3 (...)))) 

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

Кроме того, в настоящее время ваша формула является неформальной. Вы должны попробовать преобразовать его в реальное повторение.

---

Возвращаясь к вашему вопросу, я получаю впечатление, что ваш объект вроде как дерева узлов и при обходе этого дерева, чтобы преобразовать Int в нечто другое. В этом случае было бы легче найти сложность, если посмотреть на свои структуры данных, а не пытаться сделать повторение. Например, если мы знаем, что каждый узел исходного объекта заканчивается обработкой один раз, то (если у нас есть n узлов), наша общая продолжительность выполнения будет в n раз больше затрат на обработку одного узла. Если для обработки узла преобладает время, необходимое для поиска конвертера, то сложность обработки узла равна O (m), где m - количество преобразователей. С другой стороны, если затраты на выполнение этого узла (после того, как вы уже конвертировали дочерние узлы) больше, чем это, вы игнорируете стоимость поиска конвертера и используете его вместо этого.

Предполагая, что, если вы закончили узел, когда вы прошли, то это дешево (скажем, постоянное время), то наша общая временная сложность - это O (n * m), где n - количество узлов, а m - количество преобразователей. Теперь нам просто нужно преобразовать это в что-то в терминах N. Если оба n и m равны O (n) (taht is, и список объектов и преобразователей такой большой, какой мы хотим), тогда сложность будет O (N^2). Если объект такой же большой, как мы хотим (n - O (N)), но список преобразователей имеет ограниченный размер (m - O (1)), то n * m равно O (N). И так далее.