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

Question

我在这里有一个函数来计算数组中唯一整数对的数量,其总和是偶数.目前我使用嵌套循环对此进行了编码,但这是低效的,因为嵌套循环会导致时间复杂度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]在这方面.

Answer 1

您可以通过两种方式获得均数:

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).