蟒蛇 - 熊猫 - O（）大O复杂的分组和总结数据帧

分组和求和会增加循环的大O复杂度吗？蟒蛇 - 熊猫 - O（）大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

来源

2016-11-03 Chris

检查实施。如果您不知道实施情况，很难推断复杂性。尽管在这里你可能会想到'DataFrame.sum（）'可能会做什么。 _you_如何实现'sum（）'方法？ –

@ Christoph Terasa - 让我们说如果将变量传递给变量并且使用变量如* sum（A）+ b * sum（B）+ c * sum（C）进行一些算术运算，以获得总值每个数据帧。 – Chris

这个问题有什么问题来降低它的投票呢？ – Chris

一切都取决于和的执行（是幼稚的，不是高速缓存的东西？做懒的评价？）。但在一般的循环的复杂性：

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)，但由于您每次迭代刷新数据，情况并非如此，但您仍然可以使用增量更新进行求和的数据结构（因为如果修改结构中的单个行，总和就会以简单的方式变化）。然后，你可以有

comp(sum_i) = O(elements_modified_in_ith_iteration)

，然后如果你认为你在每次迭代中最M元素修改，你必须的.sum操作是知道你O(NM)的更新。

据我所知熊猫.sum是天真的方法，因此它会有复杂性（假设你的容器最多有K元素）。但是，如果你的容器增长，例如添加在每个迭代D元素，那么你得到

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

和整个循环变得

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

这是N二次。

来源

2016-11-04 22:52:41 lejlot

蟒蛇 - 熊猫 - O（）大O复杂的分组和总结数据帧

回答

相关问题