A-A+

假设用于求平均数的算法的性能是Θ(n) 并且用于求中值的算法的性能是Θ(n lg n) 当有

2022-08-12 10:10:41 问答库阅读 195 次

问题详情

假设用于求平均数的算法的性能是Θ(n)，并且用于求中值的算法的性能是Θ(n lg n)，当有100万个数字时，用于求平均数的算法与用于求中值的算法的执行速度之比将是多少？

请帮忙给出正确答案和分析，谢谢！

参考答案

正确答案：平均值：中值=1 000 000：1 000 000*1g 1 000 000平均值：中值=1：1g 1 000 000平均值：中值=1：20求平均值比求中值要快20倍。
平均值：中值=1000000：1000000*1g1000000平均值：中值=1：1g1000000平均值：中值=1：20求平均值比求中值要快20倍。