蟒蛇 - 熊貓 - 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複雜的分組和總結數據幀

回答

相關問題