c# - 可以在比 O(n^2) 时间更好的时间内做到这一点吗？

Question

我试图解决的问题给了我一个类似的矩阵

10101
11100
11010
00101

行应该代表一个人知道的主题；例如第 1 个人，由 10101 表示，知道主题 1、3 和 5，但不知道主题 2 或 4。我需要找到一个 2 人团队可以知道的最大主题数；例如第 1 人和第 3 人的团队知道所有主题，因为在 10101 和 11010 之间，每个索引处都有 1。

我有一个 O(n^2) 的解决方案

    string[] topic = new string[n];
    for(int topic_i = 0; topic_i < n; topic_i++)
    {
       topic[topic_i] = Console.ReadLine();   
    }
    IEnumerable<int> teamTopics = 
        from t1 in topic
        from t2 in topic
        where !Object.ReferenceEquals(t1, t2)
        select t1.Zip(t2, (c1, c2) => c1 == '1' || c2 == '1').Sum(b => b ? 1 : 0);
    int max = teamTopics.Max();
    Console.WriteLine(max);

它正在通过所有未超时的测试用例。我怀疑它不够快的原因与时间复杂性有关，而不是 LINQ 机器的开销。但我想不出更好的方法。

我想也许我可以将主题索引映射到认识他们的人，比如

1 -> {1,2,3}
2 -> {2,3}
3 -> {1,2,4}
4 -> {3}
5 -> {1,4}

但我想不出从那里去哪里。

你能给我一个“提示”吗？

Answer 1

假设我们有 n 个人和 m 个主题。

我认为你的算法是 O(n^2 * m)，其中 n 是人数，因为:

1. 从主题中的 t1 得到 O(n)
2. 从主题中的 t2 得到 O(n^2)
3. t1.Zip(t2 ... 让你达到 O(n^2 * m)

我看到的一个优化是先稍微修改一下字符串:

• s1 = '0101'，其中第 i 个元素表示我是否知道第一个主题
• s2 = '1111'，其中第 i 个元素表示我是否知道第二个主题。

等...

然后你分析字符串 s1。您选择所有可能的 1 对(O(n^2) 元素)，这些 1 对显示共同知道第一个主题的人对。然后从该列表中挑选一对并检查他们是否也知道第二个主题，依此类推。如果他们不这样做，请将其从列表中删除并转到另一对。

不幸的是，这看起来也是 O(n^2 * m)，但这在实践中应该更快。对于非常稀疏的矩阵，它应该接近于 O(n²)，而对于密集矩阵，它应该很快找到一对。