CODECHEF Magic Pairs问题：n*(n-1)/2公式意义及超时优化解析

问题描述 #

给定包含n个不同整数的数组A，统计满足1≤i≤n、1≤j≤n且a_i < a_j的(i,j)对数，每个测试用例输出对应结果。

原代码的问题 #

你写的双重循环代码时间复杂度为O(n²)，当n的规模较大时（比如n=10^{4），循环执行次数会达到10}8次，远远超出程序运行的时间限制，所以会出现超时。

公式n*(n-1)/2的意义 #

因为数组中的n个元素全是不同的整数，我们可以从数学角度推导结果：

• 所有可能的(i,j)对总共有n*n个（i和j各有n种选择）。
• 其中i=j的情况有n个，此时a_i = a_j，不满足a_i <a_j的条件，需要排除。
• 剩下的n² -n = n*(n-1)个对都是i≠j的情况，对于任意一对(i,j)和(j,i)，因为元素不同，必然有且只有一个满足a_i <a_j，所以满足条件的对正好是这部分的一半，即n*(n-1)/2。

高效解法原理 #

利用数组元素全不同的特性，不需要遍历数组中的元素进行比较，直接通过数学公式计算结果。这种解法的时间复杂度为O(1)（仅需读取n的值即可计算），无论n多大，计算量都可以忽略，完全不会出现超时问题。

内容的提问来源于stack exchange，提问作者codershhoder