1

您如何计算每行代码将执行的操作数。

例子。

Algorithm find2D (A,x)
    arrLength = A.length
    for j <- 1 to arrLength – 1 do
         for k <- 1 to arrLength – 1 do
                if A[j][k] = x then
                  return true
          increment k
    increment j
return false

我想出了这个伪代码。所以我不太确定如何计算每行代码的操作次数。

因此，就像第一个循环将是 1+n 次操作一样，因为您必须设置 j，将 j 与 arrLength - 1 进行比较，它将循环 n-1 次。所以这给了你 n-1 + 1 + 1 这是 n+1 操作。

因此，对于第二个循环，即使它是嵌套的，它也会是同一件事。

我对A[j][k] = x比较有点困惑，那将是多少次操作。

谢谢。

4

3 回答 3

2

一般的经验法则是这样的：

每次遍历数组中的每个元素时，乘以 N

每次将数组一分为二，乘以 log(N)

由于您在整个数组上有两个嵌套循环，因此您是 O(N^2)。

计算常数因子比较棘手，并且取决于语言、编译器和硬件的细节。基本上只需要凭经验解决。

于 2011-01-20T21:23:18.353 回答
1

Big-Oh 是渐近的，所以你不应该关心“1+n”中的“1”。

如果您正在寻找的只是该代码的 Big-Oh 分类，只需考虑您有两个循环，一个嵌套在另一个内部，每个循环对每个元素执行一些恒定数量的操作。那么内循环是O(n)，外循环是执行内循环n次，所以外循环是O(n^2)。那么整个函数是 O(c+n^2) 其中 c 是来自外部循环周围代码的恒定操作数。由于 Big-Oh 是渐近的，因此 c 消失并且您的函数为 O(n^2)。

如果您尝试计算代码执行的确切操作数，您可能需要确定您正在使用的抽象机器。

希望这可以帮助。

于 2011-01-20T21:31:52.330 回答
0

就大 O 而言，您应该选择要计算的操作，最频繁和最原子的操作。在这种情况下，它是两个循环内的比较。您无需计算循环进行了多少次比较来进行迭代，您只需计算在最坏情况下最里面的部分将执行多少次。它将n-1为外部循环，每个n-1内部循环，给出O(n^2)总数。

于 2011-01-20T21:26:09.610 回答