算法的複雜性

Question

下面實現的算法的時間複雜度是多少？

我應該注意到，b的長度足以覆蓋作爲索引的a的元素。

void smax(int[] a, int n){  
    int[] b = new int[n]; 
    for (int i=0;i<b.length;i++){ 
     b[i]=0; 
    } 
    int m=0; 
    while (m<b.length) { 
     int k=a[0]; 
     for (int i=0;i<a.length;i++) { 
      if (a[i]> k && b[a[i]]!=1) { 
       b[a[i]]=1; 
      } 
     } 
     m++; 
    } 
    for (int i=0;i<a.length;i++){ 
     if (b[a[i]]!=1){ 
      b[a[i]]=1; 
     } 
    } 
    for (int j=0;j<b.length;j++){ 
     if (b[j]==1){ 
      System.out.println(j); 
     } 
    } 
} 

Answer 1

看起來像功課所以最好的答案將不僅是最終的答案，但也可以從中學習。

設n = a.Lengh，M = b.length個

for (int i=0;i<b.length;i++){ 
    b[i]=0; 
    } 

使得一個傳遞B的元素，因此這將有助於米步驟。

for (int i=0;i<a.length;i++){ 
    if (b[a[i]]!=1){ 
     b[a[i]]=1; 
    } 
    } 

對a的元素進行一次傳遞，所以它將貢獻n個步驟。

for (int j=0;j<b.length;j++){ 
    if (b[j]==1){ 
     System.out.println(j); 
    } 
    } 

對b的元素進行一次通過，所以它將貢獻m個步驟。

到目前爲止，我們已經2M +ñ

int m=0; 
    while (m<b.length) { 
    int k=a[0]; 
    for (int i=0;i<a.length;i++) { 
     if (a[i]> k && b[a[i]]!=1) { 
      b[a[i]]=1; 
     } 
    } 
    m++; 
    } 

爲B的每一個元素有上百萬作出貢獻的所有步驟一的元素一通。

所有步驟的總和爲2m + n + mn，其漸近表示爲O（mn）。

Answer 2

看起來像O（B * A）

Answer 3

O（LEN（B）* LEN（A））