算法输油管道问题代码及分析(3)

计算时间。

（3)如果用随机选择算法RandomizedSelect计算出中位数 median(y),然后计算n口油井到主管道的最小长度总和，则所需时间主要是随机选择算法RandomizedSelect用的时间，在平均情况下需要O(n)计算时间。

2.空间需求

算法所需的空间明显是O(n)。

所以根据比较，此算法是求解此类问题的合理算法。