0

嗨，我有两种算法需要解决它们的复杂性，我一开始自己尝试过；O(N^2) & O(N^3) 它们是：

把 Y 当作它被声明为 'y=int[N][N]' 和 B 当作 'B=int[N][N]'....

int x(int [] [] y)
{
int z = 0
for (int i =0; i<y.length; i++)
    z = z + y[i].length;
  return z;
}

int A (int [] [] B)
{
    int c =0
    for ( int i =0; i<B.length; i++)
        for (int j =0; j<B[i].length; j++)
             C = C + B[i] [j];
    return C;
}

非常感谢 ：）

4

1 回答 1

1

要计算算法复杂度，您需要计算算法中执行的操作数（big-O 表示法关注最坏情况）

在第一种情况下，您有一个执行 N 次 (y.length==N) 的循环。在循环内部，您有一个操作（在每次迭代中执行）。这与输入数量呈线性关系，因此 O(x)=N。

注意：计算 y[i].length 是一个恒定长度操作。

在第二种情况下，您有执行 N 次的外部循环（就像在第一种情况下一样），并且在每次迭代中，如果执行相同的长度 (N==B[i].length)，则执行另一个循环。在内循环内部，您有一个操作（在内循环的每次迭代中执行）。总体而言，这是 O(N*N)==O(N^2)。

注意：计算 b[i][j] 是一个定长操作

注意：请记住，对于 big-O，只有增长最快的项很重要，因此可以忽略加法常数（例如，返回值的初始化和返回指令都是操作，但都是常数，而不是在循环中执行；取决于 N 的项增长速度快于常数）

于 2012-06-07T11:42:31.997 回答