我正在学习算法的复杂性，我得到了一个简单的算法来分析，这就是算法：
function test(int x, int y, int N){
int i, j, k;
if (x==y) {
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
commands here
}
}
for (i = 0; i < N; i++) {
commands here
}
}else {
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
for (k = 0; k < N; k++) {
commands here
}
}
}
}
}
我分析如下：
f( x， y， n( =n² + n (如果 x = y(
f( x， y， n( = n³ (如果 x ≠ y(
这意味着在最好的情况下，f(n( = n² + n 或简称 O(n²(，而在最坏的情况下，f(n( = n³或简称为 O(n³(
我的问题是：我的理解正确吗？意识到哪个函数更大是一件很直观的事情，但我是否需要在数学上比较这两个函数来证明这一点？最重要的是，模块是否正确？
谢谢，伙计们！
假设"这里的命令"是在恒定时间内执行的，那么你是对的。
您正在描述此给定算法的分段时间复杂度，具体取决于x和y的值。您已经正确地分解了这两种情况并分析了它们的复杂性，再次假设"命令"是恒定时间。现在更严格地比较这两种情况：
证明后一种情况((x!=y)(渐近大于前一种情况，(x==y)，因此是最坏的情况，就像证明N^3对于大于某个值的所有值N至少与N^2一样大一样简单。由于对于至少 0 的所有值，N^3大于N^2，因此我们可以说N^2 = O(N^3)，因此O(N^3)实际上是两种情况中最差的，因此也是最坏情况下的运行时。可以应用对称参数来显示另一种情况是最佳运行时。
您可以通过将一个运行时的极限除以另一个运行时来更快地显示相同的内容，因为N达到无穷大。如果该极限变为 0，则分子 = O(分母(，如果它变为无穷大，则反之亦然。如果它达到某个正常数，那么两者具有相同的渐近复杂性，由欧米茄符号表示。
渐近记谱法的简要回顾
如果你对X和Y的分布有所了解，你可以深入研究平均情况分析，因为你将能够确定最坏/最佳情况发生的概率。