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

Question

如果满足一定的条件，counting-sort算法可以在线性时间内进行排序。构造一个序列A =< a1；：：：；a10 > of n= 10，其中计数排序需要theta(n^7)时间。解释你的选择。

我的方法；

如果我选择A= 0,0,0,1,2,3,4,5,6,2，2，3，4，5，6，其中n=10 C是3,4,6, 7 ,8,9,10，B= 0,0,0,1,2,2,3,4,5,6这就是计数排序的工作方式(根据讲座)，但是我如何证明它的运行时间是n次方7呢？根据伪代码计算每一步的运行时间，然后添加？

Answer 1

选择A[]，使范围为n^7，在本例中为10^7。它可以是A[] = {0,0,0,0,0,0,0,0,0,9999999}；。由于计数数组大小为10^7，因此对数组进行一次扫描以生成输出将需要10^7次循环。