算法的复杂性

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））