问题描述
我有一个Java函数，该函数接收一个矩阵（二维array [] []），并为该数组的更改创建动态选项数组，然后为该动态数组的每个选项递归创建一个动态数组。 最终，对于N个选项之一的每个选项，它还会创建N个其他选项。
被告知，其时间复杂度的函数为T（n）= T（n）* n，这可能吗？大O表示形式的渐近时间复杂度是什么？
I have a Java function that receives a matrix (2-dimensional array[][]) and creates a dynamic array of options of changes for this array, and then recursively creates a dynamic array for each option of the dynamic array. Eventually for each option in one of N options it creates N other options.I was told that the function of time complexity of it is T(n)=T(n)*n, is this possible? And what is the asymptotic time complexity of it in big O notation?
推荐答案
如果递归关系为T（n）= nT （n）那么递归永远不会停止。这种重复关系意味着每个子问题的大小都与原始问题相同。在递归函数中，如果每个子问题的大小与原始问题的大小相同，则意味着递归不会结束。从您的问题看来，您的函数在原始矩阵上运行一次，然后在第一个函数应用程序的结果运行一次，然后停止。那不是真正的递归函数，也不是真正适合计算时间复杂度的递归关系模型。不过，计算时间复杂度也非常简单，因为您实际上可以将所有计算加起来。
If the recurrence relation is T(n)=nT(n) then the recursion never halts. That recurrence relation implies that every subproblem is the same size as the original problem. In a recursive function, if every subproblem is the same size as the original problem, that means that the recursion doesn't end. From your question it sounds like your function works once on the original matrix and then once on the results of the first function application, and then stops. That's not really a recursive function, and doesn't really fit the recurrence relation model for computing time complexity. It's also very simple to compute the time complexity of, though, because you can really just add up all of the computations.
这篇关于递归函数的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！