递归算法的时间复杂度
我有一个带有 x 边字段的网格。每个字段都包含一个指向其 x 周围字段的链接。 [x 是常数]
我有一个在该领域实现的算法（可能可以优化）：
[java 类似伪代码]
public ArrayList getAllFields(ArrayList list) {
list.addToList(this);
for each side {
if ( ! list.contains(neighbour) && constantTimeConditionsAreMet()) {
neighbour.getAllFields(list) //Recursive call
}
}
return list;
}
我无法找到时间复杂度。
ArrayList#contains(Object) 以线性时间运行我如何找到时间复杂度？我的方法是这样的：
T(n) = O(1) + T(n-1) +
c(nbOfFieldsInArray - n) [The time to check the ever filling ArrayList]
T(n) = O(1) + T(n-1) + c*nbOfFieldsInArray - cn
这会给我 T(n) = T(n-1) + O(n) 吗？
I have a grid with x-sided field in it. Every field contains a link to it's x surrounding fields. [x is constant]
I have an algorithm which is implemented in this field, (which can probably be optimized):
[java like pseudocode]
public ArrayList getAllFields(ArrayList list) {
list.addToList(this);
for each side {
if ( ! list.contains(neighbour) && constantTimeConditionsAreMet()) {
neighbour.getAllFields(list) //Recursive call
}
}
return list;
}
I'm having trouble finding the time complexity.
ArrayList#contains(Object) runs in linear timeHow do i find the time complexity? My approach is this:
T(n) = O(1) + T(n-1) +
c(nbOfFieldsInArray - n) [The time to check the ever filling ArrayList]
T(n) = O(1) + T(n-1) + c*nbOfFieldsInArray - cn
Does this give me T(n) = T(n-1) + O(n)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您添加到代码中的注释没有帮助。
getContinent是做什么的？无论如何，由于您对列表中的每个潜在添加项都使用线性搜索 (
ArrayList.contains)，因此看起来复杂度将为 Omega(n^2)。The comment you added to your code is not helpful. What does
getContinentdo?In any case, since you're using a linear search (
ArrayList.contains) for every potential addition to the list, then it looks like the complexity will be Omega(n^2).您的重现似乎是正确的
T(n) = T(n-1) + theta(1)。如果您绘制递归树，您会发现有一个分支，其值为
theta(n-1)、theta(n-2)、...、theta(2)、theta(1)，如果将所有级别相加，您将得到 算术级数 1+2+3+...+n如果您定义
并计算
S1+S2，您将得到，这
意味着
T(n ) = 1/2 θ(n(n-1)) = 1/2 θ(n^2) = θ(n^2)You recurrence seems correct
T(n) = T(n-1) + theta(1).If you draw the recursion tree you'll notice you have a single branch with the values
theta(n-1), theta(n-2), ..., theta(2), theta(1), if you add up all the levels you get the arithmetic series 1+2+3+...+nIf you define
and then calculate
S1+S2you gettherefore
which means
T(n) = 1/2 theta(n(n-1)) = 1/2 theta(n^2) = theta(n^2)