本节给出了几个确定重复、序列和选择语句的 Big O 的示例。
考虑以下循环的时间复杂度：
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 倍。执行结果证实了预测。
以下循环的时间复杂度是多少？
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) 的算法称为二次算法，它表现出二次增长率。随着问题规模的增加，二次算法会快速增长。如果将输入大小加倍，算法的时间就会增加四倍。具有嵌套循环的算法通常是二次的。
考虑以下循环：
for (int i = 1; i
for (int j = 1; j
k = k + i + j;
}
}
外循环执行n次。对于 i = 1, 2, c ，内循环执行一次、两次和 n 次。因此，循环的时间复杂度为
考虑以下循环：
for (int i = 1; i
for (int j = 1; j
k = k + i + j;
}
}
内循环执行20次，外循环执行n次。因此，循环的时间复杂度为
T(n) = 20*c*n = O(n)
考虑以下序列：
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)
考虑以下选择语句：
if (list.contains(e)) {
System.out.println(e);
}
其他
for (对象 t: 列表) {
System.out.println(t);
}
假设列表包含n个元素。 list.contains(e) 的执行时间为 O(n)。 else 子句中的循环需要 O(n) 时间。因此，整个语句的时间复杂度为
考虑整数 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中文网其他相关文章！
