确定合并排序的呼叫(激活)次数 [英] Determining number of calls (activations) to mergesort

问题描述

我正在为CS 125期末考试而学习，而Big O Notation被简要介绍了.

鉴于:

• Mergesort的运行时间最佳情况为O(N lg(N))，而运行时间最差情况为O(N lg(N))
• 有32个浮点值，最初以随机顺序存储在双精度数组中

如果要对数组进行排序，将有多少次对mergesort的调用(激活)?假设基本情况对单个值进行排序.

我会继续说，只需插入32个最坏情况或最佳情况(因为mergesort保证O(N lg(N)).

这不能为我提供正确的解决方案(显然是31).有人可以提供一些指示或解释吗?我只是看不到.

解决方案

由于32是2 ⁵ ，因此递归树将是完整的二叉树.然后，我们对mergesort进行1 + 2 + 4 + 8 + 16 + 32 = 63调用.对我来说，目前尚不清楚为什么答案会是31，而当他们指出基本情况是长度1时.显然，他们没有计算递归的最后一级(或者他们假设当长度为1时就不会递归). /p>

在最初的尝试中，您将运行时间与递归调用混淆了. Mergesort的O(n log n)是算法进行的元素间比较数量的上限.当我们要计算递归调用的次数时，知道此界限对我们没有任何好处(尽管知道算法 的工作原理).

I'm studying for a CS 125 final exam, and Big O Notation was covered (briefly).

Given that:

• Mergesort has a Running Time Best Case of O(N lg(N)) and Running Time Worst Case of O(N lg (N))
• There are 32 floating point values, initially in random order, stored in a double array

How many total calls(activations) to mergesort will there be if the array is to be sorted? Assume the base case sorts a single value.

I would go ahead and say simply plug in 32 to the worst case or best case (as mergesort guarantees O(N lg (N)).

This does not give me the correct solution (which is apparently 31). Can someone provide some pointers or an explanation? I just don't see it.

解决方案

As 32 is 2⁵, the recursion tree will be a full binary tree. We then do 1 + 2 + 4 + 8 + 16 + 32 = 63 calls to mergesort. It is unclear to me why the answer would be 31, when they state the base case is length 1. Apparently they don't count the last level of recursion (or they assume you don't recurse when the length is 1).

In your original attempt, you are confusing running time with recursive calls. Mergesort's O(n log n) is an upper bound on the number of comparisons between elements the algorithm makes. As we want to count the number of recursive calls, knowing this bound doesn't do us any good (although knowing how the algorithm works does).

这篇关于确定合并排序的呼叫(激活)次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！