logo标签列表

时间复杂度 - 将O(N²)重构为O(N)

c#arraysalgorithmbig-otime-complexity
3
我这里有一个函数，它可以计算数组中唯一整数对的数量，这些整数对的和是偶数。目前我使用嵌套循环编写了此代码，但这种方法效率低下，因为嵌套循环的时间复杂度为O(N²)。
在这个例子中，A代表数组，P和Q代表整数对。Q应该始终大于P，否则会导致非唯一整数对（其中P和Q可以指向数组中的同一个值）。
public int GetEvenSumCount(int[] A)
{
    // result storage
    int result = 0;

    // loop through each array element to get P
    for (int P = 0; P < A.Length; P++)
    {
        // loop through each array element to get Q
        for (int Q = P + 1; Q < A.Length; Q++)
        {
            // calculate whether A[P] + A[Q] is even.
            if ((A[P] + A[Q]) % 2 == 0)
            {
                result++;
            }
        }
    }
    return result;
}

现在我需要重构这个代码，使得最坏时间复杂度为O(N)，但是我不知道从哪里开始！我知道这将涉及到只使用一个循环，而不是嵌套循环，但是我不知道如何在此情况下对A[P]和A[Q]进行求和。

1
显然，你不能通过明确地访问每一对来完成它。但是你不必这样做。我会回报解决方案。 - harold
这不会是Twitter的面试题吧？ - templatetypedef
@templatetypedef，这是一个面试问题，但不是针对Twitter的。 - Matthew Layton
7个回答
5
你可以通过两种方式获得一个偶数总和:
  1. 将两个偶数相加，比如 2 + 4 = 6
  2. 将两个奇数相加，比如 1 + 3 = 4
相反，将一个偶数和一个奇数相加总是会得到奇数，比如 1 + 2 = 3 因此，你可以得到的偶数和的总数为:
  1. 偶数值对的数量
  2. 再加上奇数值对的数量
在一个包含 n 个项目的集合中，你拥有的配对数量为:
N = n * (n-1) / 2

完整代码：

static bool IsEven(int i)
{
    return i % 2 == 0;
}

static bool IsOdd(int i)
{
    return i % 2 != 0;
}

static int GetPairCount(int n)
{
    return n * (n- 1) / 2;
}

public static int GetEvenSumCount(int[] A)
{
    int evensCount = A.Count(IsEven);
    int oddCount = A.Count(IsOdd);

    return GetPairCount(evensCount) + GetPairCount(oddCount);
}

正如你所看到的，这里没有嵌套循环，也不需要实际计算总和。

这种实现的复杂度为O(N)。

2

两个整数的和只有在两个数均为偶数或均为奇数时才可能是偶数。

扫描这个数组，统计其中奇数和偶数的数量。设它们分别为N1和N2。

The number of pairs = (N1 Choose 2) + (N2 Choose 2).
                    = N1*(N1-1)/2 + N2*(N2-1)/2
谢谢你的回答，帮了我很多！你能解释一下为什么要这样做吗：N1*(N1-1)/2 + N2*(N2-1)/2？我知道它有效，但我不明白这是在做什么？ - Matthew Layton
2
这是从n个物品中选择2个物品的方式数量，顺序不重要。C(n,2)。如果您想获取更多信息，可以搜索排列组合，或访问此链接http://www.mathsisfun.com/combinatorics/combinations-permutations.html。 - Abhishek Bansal
1
按照承诺，回报解决方案：

static int GetEvenSumCountFast(int[] A)
{
    int[] OddEven = new int[2];
    for (int i = 0; i < A.Length; i++)
        OddEven[A[i] & 1]++;
    return OddEven[0] * (OddEven[0] - 1) / 2 +
        OddEven[1] * (OddEven[1] - 1) / 2;
}

我知道其他人已经解决了这个问题，但无论如何...

替代方案：

static int GetEvenSumCountFast(int[] A)
{
    int odd = 0, even = 0;
    for (int i = 0; i < A.Length; i++)
    {
        odd += A[i] & 1;
        even += ~A[i] & 1;
    }
    return odd * (odd - 1) / 2 +
        even * (even - 1) / 2;
}
嗨，我注意到你有一个“快速”的例子。这比O（N）时间复杂度更快吗？ - Matthew Layton
不，它们都是O(N) - “快”的，因为它们比O(N^2)更快。你不能用少于O(N)的时间完成它，最坏情况下你必须查看所有输入。 - harold
1

由于两个偶数的和是偶数，两个奇数的和也是偶数（但一个奇数和一个偶数的和是奇数），所以我首先将它们分成偶数和奇数两组：

var grouped = A.GroupBy(x => x % 2 == 0);

现在每个由n个元素组成的组中唯一对数为：

(n-1) + (n-2) + … + 1 = n * (n-1) / 2

所以（无论我们处于偶数组还是奇数组）：
return gouped.Sum(x => {var n = x.Count(); return n * (n-1) / 2; });
0
感谢所有为这个问题做出贡献的人，我已经将你们的所有笔记整理在一起，编写了一个简洁的函数，它的行为符合预期，并且仍然符合所需的O(N)时间复杂度。
public int GetEvenSumCount(int[] A)
{
    int odd = A.Count(o => o % 2 != 0);
    int even = N.Length - odd;
    return odd * (odd - 1) / 2 + even * (even - 1) / 2;
}
0

嗯，我有一个O(n)的解决方案。有点作弊，你可以这么认为。

"int"有限制范围-+/-2^31。

我们必须假设可能的数组大小是无限的-否则O()符号就没有意义了。如果数组大小被限制在比如2^64个元素，那么问题总是可以在常数时间O(1)内使用2^128个操作来解决...

因此，创建一个包含在数组中的所有可能的2^32个int值的位图。这需要O(n)步骤。从位图创建一个新数组，删除所有重复项。该数组最多有min(n, 2^32)个条目。其余部分总是可以在2^64个操作中完成，这是O(1)。因此，总体上是O(n)，但如果n约为2^32，则具有巨大的常数因子。

如果数组包含字节而不是整数，这实际上是一种相当快速的算法。

现在找到一个高效的算法似乎有点困难。

0
问题是要找到唯一的偶数和...在所有上述解决方案中...当计算奇数和偶数数字的数量时，它们没有考虑它们的独特性。例如，如果有两个具有相同值的偶数，比如4和另一个偶数6。将会有两个值为10的偶数和，它们是非唯一的。
我理解你的观点，但那可能并不重要。此外，那只是一个面试问题，上面的答案仍然是错误的！:-P - Matthew Layton
PS：实际上有四个值为10的偶数和，而不是两个...为什么？第一个4和第一个6，第一个4和第二个6，第二个4和第一个6，第二个4和第二个6 :-) - Matthew Layton
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接