2015-04-02 51 views
0

的代碼的複雜性。根據我的教授,這個代碼是泰塔(N^N)由線衡量一個遞歸函數

測量線路,我不能發現自己,爲什麼它的N 1,N複雜

這是代碼

any(v[], n, degree){ 
    for(i=0; i<degree; i++){ 
     any(v,n-1,degree) 
    } 
} 

我一直在做我自己。

any(v[], n, degree){ 
    for(i=0 - C; i<degree c(n+1); i++ cn){ 
     any(v,n-1,degree) n(T(n-1)) 
    } 
} 

這是2c+2cn+n(T(n-1))

回答

1

首先,它看起來像這實際上是無限的,因爲它不會破壞或在n == 0處返回。假設算法在n == 0處返回(它必須在當前缺少的if語句中):

T(n)=度* T(n-1),其中T(0)= 1和T(1)=度

這降低了O(度^ N)

我真的不知道其中N^N從何而來。除非我把數學做錯了。

+0

在這一點上沒問題。 T(n-1)在這種情況下的分辨率是多少? – 2015-04-03 22:59:56

1

你的教授是對的,代碼會永遠遞歸地調用自己,並且變得負面。如果這是不是你想要的,那麼你就必須實現的條件結束遞歸,即,n值:

any(v[], n, degree){ 
    if (n > -1) { 
     for(i=0;i< degree;i++){ 
      any(v,n-1,degree) 
     } 
    } 
}