算法-涉及if语句时如何计算时间复杂度

Question

我是算法的新手，有一个关于如何在有 if 语句的情况下计算时间复杂度的问题。我有一个在堆中实现的优先级队列。这是出列方法:

int[] pQueue;
int length; 
int dequeue()
{
     int node = 1;
     int value = pQueue[--length];
     int maxValue = pQueue[node];

     int location = sift(node * 2, value);
     pQueue[location] = value;
     return maxValue;
}

int sift(int node, int value){
     if (node <= length){
         if (node < length && pQueue[node] < pQueue[node + 1])
         node++;
     if (value < pQueue[node]){
         pQueue[node / 2] = pQueue[node];
         return sift(node * 2, value);
         }
}
     return node / 2;
}

在sift方法中，有两行代码:

         if (node < length && pQueue[node] < pQueue[node + 1])
         node++;

既然n++是按上面的条件执行的，那么推导递归方程时要算还是不要算呢？我知道它确实会渐近地产生任何影响，但是有没有标准的方法可以做到这一点？非常感谢。

Answer 1

标准方法是在条件取决于所考虑的变量时将其考虑在内。例如，考虑一个在 if 语句中调用自身的简单递归函数:

double factorial(int n) {
    double result = n;
    if (n > 0) {
        result *= factorial(n - 1);
    }
    return result;
}

如果我们假装总是满足 if 条件，则递归是无限的，复杂度是无限的(不管 n)。如果我们假装从未满足 if 条件，则递归调用永远不会发生，并且复杂度是恒定的。显然，这些都不是可以接受的借口。复杂度实际上是 O(n)。

当条件不取决于正在考虑的变量时，标准方法通常是给出最坏情况的复杂性(并表明我们正在这样做)。例如，对于排序算法，我们通常根据要排序的序列的长度给出复杂度，但是许多排序算法的执行方式不同，具体取决于元素的初始排序。因此，我们假设我们感兴趣的是它们对长度具有最不有利排序的序列的性能，并进行相应的计算。

(通常也可以提供平均情况复杂度，但是，通过对所有可能的输入进行平均，有时甚至是典型情况复杂度。)