algorithm - 计算数组的经验CDF的数值复杂度是多少？

都在标题里。假设$x$是n个浮点数组。empirical CDF是t的函数：

Fn(t) = (1/n) sum{1{Xi <= t} : i=1,...,n}

必须计算t_1<t_2,...,t_m（例如，m different，sorted，value of t）我的问题是计算这个问题的数值复杂度是多少？我认为o（nlog（n））+o（mlog（n））[对数组排序，然后执行m个二进制搜索，每个值为t]
但我可能太天真了有人能证实吗？
编辑：
很抱歉弄得一团糟在写这个问题的时候，我意识到我施加了一些不在原来问题中的约束。我在下面回答伊夫的问题。
Xi没有分类。
t_j被排序并等距分布。
m小于n，但不是按震级排列的：通常为m~n/4。

最佳答案

给定的表达式是N0/1项的总和，显然是O(N)。
更新：
如果Xi是预先排序的，那么函数就很小，而且计算是以某种方式进行的！
如果CDFi = CDF(Xi) = i/N未排序，则需要在O(0)中首先排序，除非变量的范围允许更快的排序，例如计数排序。
如果您只需要计算少量的Xis，让O(N.Log(N))，那么您可以考虑使用简单的求和，因为Xi可以胜过K。
更新：（OP的第二次更改）
否则，必要时对K.N进行排序，必要时对N.Log(N)进行排序那么一个单一的线性通道就足够了总的复杂性将是：

O(n.Log(n) + m.Log(m))
O(n.Log(n) + m)
O(n + m.Log(m))
O(n + m).

如果Xi和tj未排序，请使用天真的公式。复杂性m < Log(n)
当Xi时可能有更好的选择。
更新：最终规格：O(m.n)未排序，m>n排序，Xi。
我选择的解决方案如下：
1）对Tj进行排序。
2）“合并”已排序的m < n和Xi。这意味着，在Xi和Tj列表中同时进行，保持两个正在运行的索引；确保总是增加导致最短移动的索引；使用X。这是一个线性过程。（非常接近合并排序中的合并。）
全局复杂度为T，合并项CDF(Tj)=i/n被吸收。
更新：统一采样。
当O(n.Log(n))值是等距的，让O(n)时，可以使用直方图方法。
分配一个Tj计数器数组，最初为Tj = T0 + D.j。对于每个m+1，将bin索引计算为0。将负值钳制为Xi，将大于Floor((Xi - T0) / D)的值钳制为0增加那个箱子。最后，每个bin都会告诉您在m范围内有多少个m值。
计算计数器的前缀和。它们现在将告诉您有多少X值小于[Tj, Tj+1[和X。
[注意，这是未经检查的草图，可能在细节上有误。]
总计算将采用Xj+1bin递增，然后是CDF(j)=Counter[j]/n元素的前缀和，即n操作。

# Input data
X= [0.125, 6, 3.25, 9, 1.4375, 6, 3.125, 7]
n= len(X)

# Sampling points (1 to 6)
T0= 1
DT= 1
m= 6

# Initialize the counters: O(m)
C= [0] * m

# Accumulate the histogram: O(n)
for x in X:
    i= max(0, int((x - T0) / DT))
    if i < m:
        C[i]+= 1

# Compute the prefix sum: O(m)
S= 0
for i in range(m - 1):
    C[i + 1]+= C[i]

# Reduce: O(m)
for i in range(m):
    C[i]/= float(n)

# Display
print "T=", C

T=[0.25，0.25，0.5，0.5，0.5，0.75]

关于algorithm - 计算数组的经验CDF的数值复杂度是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23951540/

xi

algorithm - 计算数组的经验CDF的数值复杂度是多少？