python

Question

分组求和会增加循环的Big O复杂度吗？

假设分组和求和是 n 循环的一部分，其中数据框在每次迭代时都用新数字刷新。

循环已经是 O(n) 的复杂度。分组和求和是否增加了这里的复杂性？

有个例子

import pandas as pd

V=[(1, 2, 3, 4, 5,), (6, 7, 8, 9, 10)]
A=['A','B','C','A','B']
T=[]
n=2

for k in xrange(n)

   df = pd.DataFrame({"class":A, "value":V[k]})

    S1=df[df["class"]=='A'].sum()["value"]
    S2=df[df["class"]=='B'].sum()["value"]
    S3=df[df["class"]=='C'].sum()["value"]  

    T[k]= 1* S1 + 2* S2 + 3* S3      


#---------------------------------------------------
#for example if k==0

df 
         class  value
     0     A      1
     1     B      2
     2     C      3
     3     A      4
     4     B      5

    df[df["class"]=='A'].sum()["value"]
    5
    df[df["class"]=='B'].sum()["value"]
    7
    df[df["class"]=='C'].sum()["value"]
    3
    T
    28

Answer 1

一切都取决于求和的实现（它是否天真，它是否缓存东西？做惰性评估？）。但总的来说，你的循环复杂度是：

O(N * comp(sum))

或更严格地说

O(SUM_i comp(sum_i) )

现在，简单的实现

comp(sum_i) = comp(sum) = O(K)

其中 K 是容器中元素的数量。因此整个循环是 O(NK)

但是，如果总和在调用之间始终相同（结构没有任何变化）并且您在求和调用之间进行缓存，您会得到

comp(sum_1) = O(K)
comp(sum_i) = O(1)   i>1

因此整个循环是 O(N+K)，但由于你是 "refreshing data every iteration"，情况并非如此，但你仍然可以拥有一个数据结构，它对 sum 进行增量更新（因为如果你修改结构中的单行，总和以简单的方式变化）。那么，你可以

comp(sum_i) = O(elements_modified_in_ith_iteration)

然后，如果您假设在每次迭代中最多修改 M 个元素，并且您有 .sum 操作，它知道您获得 O(NM).

的更新

据我所知 pandas .sum 是天真的方法，因此它将具有 O(NK) 复杂性（假设您的容器最多有 K 个元素）。但是，如果您的容器增长，例如您在每次迭代中添加 D 个元素，那么您会得到

comp(sum_i) = O(K + i*D)

整个循环变成

O(SUM_i comp(sum_i)) = O(N(K + D(N+1)/2))

这是 N 的二次方。

python - pandas - O() 对数据帧进行分组和求和的大 O 复杂度

python - pandas - O() Big O complexity of grouping and summing a data frame

big-o

time-complexity

dataframe

pandas