algorithm - 从 n^2 减少时间复杂度

Question

类(class)里有 n 个学生。很快，将有一个校际科学测验，其中将有 4 个主题的问题，为简单起见，将它们称为 1、2、3 和 4。一个团队应该有2名学生。任何学生在某一特定科目上表现出色或表现不佳的可能性均等。

我们有 n 行作为输入，每行有 4 个条目。如果第 i 列等于 1，则该学生擅长第 i 科目。我应该找出学校的总方法数可以派一个小组，让两个学生一起知道所有 4 个科目。

例如，

S1: 1 1 1 1
S2: 1 1 0 1
S3: 1 0 1 1
S4: 0 0 1 1
S5: 0 0 0 0

学生 1 可以和任何学生一起去，因为所有科目都是他的强项。 => 4

学生 2 可以选择 S3 和 S4，因为 S2 在科目 1,2 和 4 上表现不错，而 S3 和 S4 在科目 3 上表现不错。=> 2(请注意，(S1,S2) 已经计算在内)

S3 将与擅长科目 2 的人一起去=> 无

S4:同样，没有。

因此，ans=4+2=6

我的解决方案:-

ans=0;
//arr is the array containing subject-wise "strength" of students
for(int i=0;i<n;i++){
    ArrayList<Integer> a=new ArrayList<>();
    for(int j=0;j<4;j++)
        if(arr[i][j]==0)
            a.add(j);
    if(a.size()==0)
        ans+=n-i-1;
    else
        for(int j=i+1;j<n;j++){
            bool=false;
            for(int k=0;k<a.size();k++){
                if(arr[j][a.get(k)]==0)
                    break;
                bool=true;
            }
            if(bool)
                ans++;
        }
}
System.out.println(ans);

现在我知道我的解决方案是正确的，但它的时间复杂度是 O(n^2)，我正在寻找更好的解决方案。谢谢!

Answer 1

您可以通过为科目组合花费内存来降低学生数量的复杂性。

构建一个包含 2^s 个元素的列表，其中 s 是主题的数量。通过主题组合索引列表，解释为二进制数。例如，S2 的值为 13，缺少值 2。

首先统计每个学生可以满足的“需求”。对于学生已知科目中 1 位的每个组合，增加计数列表的索引。

for student in student_list:

    score =   # student's covered subjects as an int

    tally = [0]*16
    for idx in range(16):
        if idx & score == idx:
            tally[idx] += 1

您现在有一个列表，其中列出了有多少学生可以涵盖所需科目的每个组合。这是O(n * 2^s)

对于每个学生，找到需要的分数，即学生分数的 1 的补码。现在为所需分数添加所有计数是一件简单的事情。

team_ct = 0

for student in student_list:

    needed =   # student's needed subjects as an int; this is 15-score (above)
    team_ct += tally[needed]

现在，每个配对都被计算了两次，所以将 team_ct 除以 2。是的，最后一段代码可以放在一行中:

team_ct = sum([tally[15-score] for score in foo]) / 2

其中 foo 是所有学生分数的构造。这部分是O(n)。