我认为复杂度是 O(n^2)。我错了吗?如果是这样,您能解释一下原因吗?
public int countXs(char[][] m)
{
int rows = m.length, cols = m[0].length;
int r = 0, c = 0, count = 0;
while (r < rows || c < cols)
{
count += r;
while (r < rows && m[r][c] == 'x')
{
count++;
r++;
}
c++;
}
return count;
}
最佳答案
首先,您的代码可能会因c
索引的arrayIndexOutofBound
而崩溃。
接下来,当你投入时间复杂度时,首先需要定义什么是n
。通常n
表示输入的大小,在本例中n
是二维数组的大小。
因此,您需要设置时间复杂度公式并指定代码的最坏情况来计算时间复杂度。假设数组 m
为 pxq (p + q = n)
并且我们表示 O(1) = 1
。
T(n) = Sum(i->max(p, q)) {1 + sum(j->p)(1)}
= max(p,q) + sum(i->max(p,q)){p}
= max(p, n-p) + sum(i-> max(p, n-p)) {p}
= max(p, n-p) + p(n-p)
4*ab <= (a+b)^2 we have: p(n - p) < (p + n - p)^2 /4 = n^2/4
所以:
T(n) <= n + n^2/4 = O(n^2) . Q.E.D
关于java - 这段代码的复杂度是 O(n^2) 还是 O(n^2 * n^(1/2))?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28575593/