查找给定java代码的时间和空间复杂度
问题描述:
您好我需要找到程序的时间和空间复杂度,请帮助,如果可能的话请提出可以执行的优化, ........ .................................................. .................................................. .................................................. ...........................查找给定java代码的时间和空间复杂度
public class Sol {
public int findMaxRectangleArea(int [][] as) {
if(as.length == 0)
return 0;
int[][] auxillary = new int[as.length][as[0].length];
for(int i = 0; i < as.length; ++i) {
for(int j = 0; j < as[i].length; ++j) {
auxillary[i][j] = Character.getNumericValue(as[i][j]);
}
}
for(int i = 1; i < auxillary.length; ++i) {
for(int j = 0; j < auxillary[i].length; ++j) {
if(auxillary[i][j] == 1)
auxillary[i][j] = auxillary[i-1][j] + 1;
}
}
int max = 0;
for(int i = 0; i < auxillary.length; ++i) {
max = Math.max(max, largestRectangleArea(auxillary[i]));
}
return max;
}
private int largestRectangleArea(int[] height) {
Stack<Integer> stack =
new Stack<Integer>();
int max = 0;
int i = 0;
while(i < height.length) {
if(stack.isEmpty() ||
height[i] >= stack.peek()) {
stack.push(height[i]);
i++;
}
else {
int count = 0;
while(!stack.isEmpty() &&
stack.peek() > height[i]) {
count++;
int top = stack.pop();
max = Math.max(max, top * count);
}
for(int j = 0; j < count + 1; ++j) {
stack.push(height[i]);
}
i++;
}
}
int count = 0;
while(!stack.isEmpty()) {
count++;
max = Math.max(max, stack.pop() * count);
}
return max;
}
预先感谢您
答
要找到空间复杂度来看看在你声明的变量上,并且大于单个原始变量。事实上,我相信你的空间复杂性将决定我的阵列auxilary
和Stack
stack
。第一个的大小非常清晰,我不完全理解第二个,但是我发现它的大小永远不会比数组大。所以我想说的空间复杂性是O(size of(auxilary))
或O(N * M)
其中N=as.length()
和M = as[0].length
。
现在时间复杂度有点棘手。您在整个auxilary
阵列上有两个周期,因此确保时间复杂度至少为O(N * M)
。您还有另一个周期,调用largestRectangleArea
为每行auxilary
。如果我正确地得到这个函数的代码,看起来这个函数再次是线性的,但我不确定这里。既然你更了解这个逻辑,你可能会更好地计算它的复杂性。
希望这会有所帮助。
任何人,请帮忙? – user2039136 2013-02-08 12:12:07
我怀疑你为什么没有得到任何回应:http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially-deprecated – alpian 2013-02-08 12:18:39
这是功课吗? – alpian 2013-02-08 12:47:36