-1

以下实现的算法的时间复杂度是多少？

我应该注意到长度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);
         }
    }
}
4

3 回答 3

2

看起来像家庭作业，所以最好的答案不仅是最终答案，也是你可以学习的答案。

设 n = a.长度，m = b.长度

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

对 b 的元素进行一次传递，因此它将贡献 m 步。

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+n

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 的每个元素，所有 a 的元素都会传递 mn 步。

所有步骤的总和为 2m+n+mn，在渐近符号中为 O(mn)。

于 2010-05-26T06:14:56.723 回答
1

O(len(b)*len(a))

于 2010-05-26T05:59:45.387 回答
0

看起来像 O(b*a)

于 2010-05-26T05:58:05.843 回答