-1

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

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;
}

因为这是归并排序，所以 big(o) 是 o(n log n)，所以 100 个整数的数组应该准确返回 200 的 big-o。柜台会去哪里？如果我把它放在 sort(..) 的顶部，我得到的平均数是 250、280、300，这应该是错误的。这个柜台的最佳位置是什么？

参考资料：http ://en.wikipedia.org/wiki/Mergesort

谢谢。

4

2 回答 2

2

因为这是归并排序，所以 big(o) 是 o(n log n)，所以 100 个整数的数组应该准确返回 200 的 big-o。

甚至没有接近正确。

使用大 Ordo 符号表示的计算复杂性并不能告诉您将准确执行多少步/计算操作。它被称为渐近复杂度而不是相同的复杂度是有原因的：它只为您提供一个函数，该函数根据输入的大小接近（更准确地说，给出更高的界限）算法的运行时间。

所以O(n log n)并不意味着对于 100 个元素，将执行 200 次操作（顺便说一句，为什么对数的底必须是 10？），它告诉您，如果您增加输入的大小，则 ( average-case) 运行时间将与添加的输入数据的数量成正比，乘以这个附加数据的数量的对数。

直截了当：如果要计算对递归函数的调用次数，则应将计数器作为参数放入，如下所示：

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 times\n", num_calls);
于 2013-03-10T06:40:12.980 回答
1

我认为您对 Big-O 表示法的概念有些误解。如果复杂度为 O(n log n) 并且 n 的值为 100，则没有严格的规定程序应该在 200 的 Big-O 中精确执行。它只给了我们一个上限。例如，考虑具有 O(n 2 ) 复杂度的选择排序。即使 n 是 100，如果列表已经排序，内部循环内设置的计数器也不会给你 100 2作为结果。因此，在您的情况下，您得到的答案（250、280、300 等）是完全有效的。因为所有答案都受到 k 乘以 n log n 的限制，其中 k 是任意常数。

于 2013-03-10T06:37:16.127 回答