我想知道计算中位数的时间复杂度常数是否与计算一般分位数不同。

以 R 为例：

fx01<-function(ll,a) quantile(a[,ll],0.75)
fx02<-function(ll,a) median(a[,ll])

n<-1000
d<-1000
a<-matrix(rnorm(n*d),n,d)

system.time(lapply(1:d,fx01,a=a))
system.time(lapply(1:d,fx02,a=a))

通常，我观察到计算一般分位数所花费的时间是中位数的 2-4 倍。我想知道这是一个实施问题还是一成不变的。