计数排序 - 我知道它是如何工作的，但无法解决它

如果满足某些条件，则计数排序可按线性时间排序。构建一个序列A = < a1; ：：：; a10> n = 10个数字，其中计数排序需要theta（n^7）时间。解释你的选择。计数排序 - 我知道它是如何工作的，但无法解决它

我的方法;

如果我选择A = [0,0,0,1,2,3,4,5,6,2]，其中n = 10 C new将是[3,4,6,7,8 ，9,10]和B = [0,0,0,1,2,2,3,4,5,6] 这是如何计算排序工作（根据讲座），但我如何证明它有运行时间n次方7？通过根据伪码计算每个步骤的运行时间，然后添加？

来源

2017-02-18 Muhammad Yousaf

看起来像一个问题给你张贴在这里。 – nullpointer

是的，因为我知道如何计数排序工作，我试着使用如下; 如果我选择A = [0,0,0,1,2,3,4,5,6,2]，其中n = 10 C new将是[3,4,6,7,8,9， 10]和B = [0,0,0,1,2,2,3,4,5,6] 这是如何计算排序工作（根据讲座），但我如何证明它已运行n次幂7？通过根据伪码计算每个步骤的运行时间，然后添加？ –

这个问题似乎是不可能解决的，因为Theta符号在极限中将运行时限作为n的函数进行讨论，所以在运行时为Theta（n^7）的情况下，应该有固定n和固定序列。对于任何固定的大小和顺序，运行时间为O（1）。 – templatetypedef

选择A []，使得范围是n^7，在这种情况下是10^7。它可能是A [] = {0,0,0,0,0,0,0,0,0,9999999} ;.由于计数阵列大小为10^7，因此对阵列进行单次扫描以产生输出将需要10^7个循环。

来源

2017-02-18 18:49:46 rcgldr

Waow ..有道理,,,一个完美的答案。万分感谢！！！我也和我的教授讨论过，他也说过一样。再次感谢你！ –

计数排序 - 我知道它是如何工作的，但无法解决它

回答

相关问题