示例：确定大 O

本节给出了几个确定重复、序列和选择语句的 Big O 的示例。

实施例1

考虑以下循环的时间复杂度：

for (int i = 1; i k = k + 5;
}

这是一个常数时间，c，用于执行

k = k + 5;

由于循环执行了n次，因此循环的时间复杂度为

T(n) = (常数 c)*n = O(n).

理论分析预测了算法的性能。为了了解该算法的执行情况，我们运行下面程序中的代码来获取 n = 1000000、10000000、100000000 和 100000000 时的执行时间。

我们的分析预测了该循环的线性时间复杂度。如示例输出所示，当输入大小增加 10 倍时，运行时间大约增加 10 倍。执行结果证实了预测。

实施例2

以下循环的时间复杂度是多少？

for (int i = 1; i for (int j = 1; j k = k + i + j;
}
}

这是一个常数时间，c，用于执行

k = k + i + j;

外循环执行n次。对于外循环中的每次迭代，内循环都会执行 n 次。因此，循环的时间复杂度为

T(n) = (常数 c)*n*n = O(n^2)

时间复杂度为 O(n^2) 的算法称为二次算法，它表现出二次增长率。随着问题规模的增加，二次算法会快速增长。如果将输入大小加倍，算法的时间就会增加四倍。具有嵌套循环的算法通常是二次的。

实施例3

考虑以下循环：

for (int i = 1; i for (int j = 1; j k = k + i + j;
}
}

外循环执行n次。对于 i = 1, 2, c ，内循环执行一次、两次和 n 次。因此，循环的时间复杂度为

实施例4

考虑以下循环：

for (int i = 1; i for (int j = 1; j k = k + i + j;
}
}

内循环执行20次，外循环执行n次。因此，循环的时间复杂度为

T(n) = 20*c*n = O(n)

实施例5

考虑以下序列：

for (int j = 1; j k = k + 4;
}

for (int i = 1; i for (int j = 1; j k = k + i + j;
}
}

第一个循环执行 10 次，第二个循环执行 20 * n 次。因此，循环的时间复杂度为

T(n) = 10*c + 20*c*n = O(n)

实施例6

考虑以下选择语句：

if (list.contains(e)) {
System.out.println(e);
}
其他
for (对象 t: 列表) {
System.out.println(t);
}

假设列表包含n个元素。 list.contains(e) 的执行时间为 O(n)。 else 子句中的循环需要 O(n) 时间。因此，整个语句的时间复杂度为

实施例7

考虑整数 n 的 a^n 计算。一个简单的算法将 a 乘以 n 次，如下所示：

结果 = 1;
for (int i = 1; i 结果 *= a;

该算法需要 O(n) 时间。不失一般性，假设 n = 2^k。您可以使用以下方案改进算法：

结果 = a;
for (int i = 1; i 结果 = 结果 * 结果;

该算法需要 O(logn) 时间。对于任意的n，你可以修改算法并证明复杂度仍然是O(logn)。

为了简单起见，由于 0(logn) = 0(log2n) = 0(logan)，所以省略了常量基数。

以上是示例：确定大 O的详细内容。更多信息请关注PHP中文网其他相关文章！