Сложность времени рекурсивной функции

Question

У меня есть функция Java, которая получает матрицу (2-мерный массив [] []) и создает динамический массив параметров изменений для этого массива, а затем рекурсивно создает динамический массив для каждого вариант динамического массива. В конце концов для каждой опции в одном из вариантов N она создает N других опций. Мне сказали, что функция временной сложности T (n) = T (n) * n, возможно ли это? И какова асимптотическая временная сложность этого в большой записи O?

Answer 1

Если рекуррентное отношение T (n) = nT (n), то рекурсия никогда не останавливается. Это рекуррентное отношение подразумевает, что каждая подзадача имеет тот же размер, что и исходная проблема. В рекурсивной функции, если каждая подзадача имеет тот же размер, что и исходная проблема, это означает, что рекурсия не заканчивается. Из вашего вопроса это звучит так, как ваша функция работает один раз на исходной матрице, а затем один раз на результаты первого приложения функции, а затем останавливается. На самом деле это не рекурсивная функция, и на самом деле не подходит модель отношения повторения для вычисления временной сложности. Также очень просто вычислить временную сложность, потому что вы можете просто добавить все вычисления.