跟踪运行时复杂度

Question

计算任何方法的运行时复杂度的最佳方法是什么?对于非递归方法很容易做到这一点，比如bubblesort

outer-for loop
{
   inner-for loop
      {
           compare and exchange
      }
}

要检查，最好的方法是在最内层循环中放置一个计数器。但是，当方法是递归的，我应该把计数器放在哪里，例如归并排序，

sort(int[] array){
    left = first-half
    right = second-half
    sort(left);
    sort(right);
   ret merge(left, right);
}
merge(int[] left, right)
{
    count = length(left + right);
    int[] result;
    loop-count-times
    {
       compare and put in result;
    }
  return result;
}

由于这是归并排序，大(0)是0 (n log n)，所以一个包含100个整数的数组应该返回一个正好是200的大0。柜台在哪里?如果我把它放在sort(…)的顶端，我得到的平均值是250,280,300，这应该是错的。这个柜台最好放在哪里?

引用:http://en.wikipedia.org/wiki/Mergesort

谢谢。

Answer 1

由于这是归并排序，大(0)是o(n log n)，所以一个100个int型的数组应该返回一个正好是200的大0。

甚至不接近右边。

使用大ordo符号表示的计算复杂度并没有告诉您将执行多少步骤/计算操作。它被称为渐近而不是相同的复杂性是有原因的:它只给你一个函数，它接近(更准确地说，给出一个更高的上限)算法的运行时间与输入的大小有关。

所以O(n log n)并不意味着对于100个元素，将执行200次操作(顺便说一下，为什么对数的底必须是10?)，它告诉你，如果你增加输入的大小，(平均情况下)运行时间将与添加的输入数据块的数量成正比，乘以这些额外数据的数量的对数。

关键是:如果你想计算递归函数的调用次数，你应该把计数器作为一个参数，像这样:

void merge_sort(int array[], size_t length, int *counter)
{
    (*counter)++;
    // apply the algorithm to `array`:
    merge_sort(array, length, counter);
}

，并像这样命名:

int num_calls = 0;
merge_sort(array, sizeof(array) / sizeof(array[0]), &num_calls);
printf("Called %d timesn", num_calls);

Answer 2

我想你对大0符号的概念有一点误解。如果复杂度为O(n log n)，且n的值为100，则没有严格的规则要求程序必须完全在Big-O(200)中执行。它只给出了一个上界。例如，考虑复杂度为0 (n²)的选择排序。即使n是100，如果列表已经排序，内循环内设置的计数器也不会给你100²作为结果。所以在你的例子中，你得到的答案(250,280,300，等等)是完全有效的。因为所有的答案都受k乘以n log n的限制，k是一个任意常数。