Блог

Главная - Вопросы по программированию - Как мы сочетаем внешнюю сложность рекурсивного алгоритма со сложностью каждого вызова?

Как мы сочетаем внешнюю сложность рекурсивного алгоритма со сложностью каждого вызова?

#algorithm #recursion #big-o

Вопрос:

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

В моем случае дополнительные шаги выполняются внутри рекурсивно вызываемой функции F(constants P, 2D matrix N) :

 function F:
  For i = 1:N
     If i satisfies condition
       Save information to a global variable
       Continue to i 1
     If i does not satisfy condition
       M = slicing of matrix N
       Call F(constants P, matrix M)
     End if
  End for
End function

Я думаю , что для глубины рекурсивности k большая часть рекурсивного алгоритма такова O(k^n) . Кроме того, я думаю, что каждый вызов функции является O(n) . Худшим случаем может быть то, что нарезка практически не удаляет какие-либо элементы матриц, так что N и M они одинаковы по размеру во всем алгоритме.

В MATLAB нарезка 2D-матриц выполняется с использованием логического индексирования, как описано в документации. Например:

 M = N(condition1 amp;amp; condition2,:);
M = N(N(:,1) > 10 amp;amp; N(:,3) - N(:,4) > 20,:);

Как вы объединяете оба понятия в одно выражение?

Комментарии:

1. Можете ли вы добавить здесь некоторые определения? Повторяю ли я матрицу строка за строкой или элемент за элементом? Как работает нарезка M?

2. Я добавил пример и ссылку на документацию в конце. Однако, поскольку я полагаюсь на встроенную логическую индексацию MATLAB, а не сам выполняю нарезку с помощью циклов, я не знаю, достаточно ли эта информация хороша для вопроса.

3. Если когда-нибудь N==M у вас будет бесконечная рекурсия.

4. Теперь я перефразировал это предложение.

5. Чтобы ответить на этот вопрос, мы должны знать, как работает нарезка. Смотрите комментарий @trincot, если N=M. Если N всегда является матрицей большего размера, чем M, то алгоритм не превышает O(n^4), но это действительно зависит от того, что такое цикл итераций и как выполняется нарезка

Метки: