递归函数的时间复杂度

Question

以大 O 表示法求下列代码的总运行时间。输入数组按大小 n 排序。

int print (int array[], int low, int high, int x){     
     int mid = (high + low) / 2;
     if (low > high)
         return -1;      //cannot find x in the array
     if (array[mid] == x)
         return mid;    // x is found
     if (array[mid] > x){
         for (int i = low; i < mid; i++)
             printf(“%d “, array[i]);
     return print(array, low, mid – 1, x);
     }
     if (array[mid] < x){
         for (int i = mid + 1; i <= high; i++)
             printf(“%d “, array[i]);
         return print(array, mid + 1, high, x);
     }
 }

递归部分与二分查找相同，所以我知道该部分的时间是 O(log n)。该程序打印出可能包含查询 x 的子数组的每个元素，那么我可以说该行的运行时间是 O(n) 吗？而代码的总运行时间只是O(n)？

递归部分（O(log n)）是否影响总运行时间？

Answer 1

输出涉及将用于递归调用的子数组。因此，每个输出都涉及当前窗口的一半，该窗口在每次递归调用时减半。这是一个几何级数，总和有一个封闭公式，在本例中以 2𝑛 为界。因此总共打印了 O(2𝑛) 数组值（以及尽可能多的空格）。

现在有两种情况需要区分：

1. 这是伪代码，对整数的大小没有限制：在这种情况下，打印单个值不是 O(1)：打印一位数字需要 O(1) 时间。打印 50 位整数比打印 2 位整数需要更多时间。因此，时间复杂度为 O(𝑑𝑛)，其中 𝑑 是输入数组中整数的平均（或最大）位数。我们也可以说它是 O(𝑛log𝑚)，其中 𝑚 是数组中的最大值，或数组中的负最小值，以较大者为准（因为可能有负值）。

2. int

   数据类型表示固定大小数据类型（如 64 位），因此我们知道此类整数的十进制表示形式对其可以拥有的位数有固定的上限。在这种情况下，打印一个整数的工作量是 O(1)，总体复杂度是 O(𝑛)。