Оценка сложности времени для алгоритма фильтрации набора данных

Question

Добрый день ...

В настоящее время я работаю над алгоритмом фильтрации для очень специфических геометрических наборов данных, и я совершенно заблудился относительно того, как оценить его временную сложность.С концептуальной точки зрения я понимаю, что сложность времени оценивается как функция от n, являющегося n входным размером алгоритма.Позвольте мне кратко описать мой алгоритм:

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

Мои вопросы: (I) Я чувствую, что n должно быть определено как количество элементов в наборе данных, но тогда я пропускаю важный фактор: количество фильтров, которые будут применены.Как я могу учитывать количество фильтров во входных данных алгоритма для оценки сложности времени?

(II) Поскольку я не могу заранее знать, сколько элементов будет стерто в каждом фильтре,Как я могу рассчитать количество операций, выполняемых алгоритмом в зависимости от n?

(III) Каждый фильтр представляет собой независимую процедуру, которую вызывает мой алгоритм, для вычисления временной сложности алгоритма, должен ли я учитывать также временные сложности каждого отдельного фильтра?Что произойдет, если фильтры определены пользователем и их сложность не может быть известна априори?

Спасибо за любые разъяснения или подсказки по этому вопросу ...

Привет.

Answer 1

Я не специалист по сложности времени, но я могу попытаться помочь вам.

Если я правильно понял, ваш алгоритм применяет N фильтров к вашим данным, возможно уменьшая данные каждый раз. Каждый фильтр применяется линейно к каждому элементу набора данных. Мы будем работать над сложностью в худшем случае, так как ее легче вычислить / понять.

Давайте использовать обозначения:

n: длина вашего набора данных до применения фильтра 1. Поскольку ваши фильтры могут только уменьшить размер вашего набора данных, в худшем случае, когда ни один фильтр не уменьшает набор данных, то есть каждый фильтр применяется к n элементам.

T: сложность вашего алгоритма

Ci: сложность i-го фильтра. Поскольку я не знаю, какие данные вы используете, я не могу быть более точным.

M: количество фильтров

Итак, имеем:

T (n, M) = n C1 + n C2 + ... + n * CM

Теперь, когда вы не знаете, какова сложность фильтра, мы не можем углубиться, так как он может сильно варьироваться. Например, если фильтр применяется к целым числам и является просто порогом, сложность составляет O (1), но если он должен проверить, является ли число a простым числом, это O (log (a) ^ 6) ...

Но если вы можете оценить наихудшую сложность среди всех ваших фильтров C_worst, используя большие обозначения Oh, мы можем получить оценку:

T (n, M) = O (M n C_worst)

Пример для целых чисел: если a - это максимум вашего набора данных, а фильтр с наихудшей сложностью является линейным на целочисленном входе, мы имеем T (n, M, a) = O (M n a)