c - 如果产品小于给定数字，则需要更快的算法来计数

Question

我有下一个问题:我的程序读取两个数组并将第一个数组的每个元素与第二个数组的每个元素相乘。我必须计算小于给定数字的结果数。我的代码工作正常，但我需要找到一个更快的算法。

这是我的代码:

void sort(int *array, int length)
{
    int index, jndex = 0, aux, compElPoz;
    for(index = 1; index < length; index++)
    {
        jndex = index - 1;
        compElPoz = index;
        while(array[compElPoz] < array[jndex])
        {
            aux = array[compElPoz];
            array[compElPoz] = array[jndex];
            array[jndex] = aux;
            if(jndex > 0)
                jndex--;
            compElPoz--;
        }
    }
}
int main()
{
    unsigned int n, in, jn, nr = 0, p, m;
    scanf("%u %u", &n, &p);
    int ar[n];//1st array
    for(in = 0; in < n; in++)
    {
        scanf("%u", &ar[in]);//reading the 1st array
    }
    scanf("%u", &m);
    int arr[m];//2nd array
    for(in = 0; in < m; in++)
    {
        scanf("%u", &arr[in]);//reading the 2nd array
    }
    sort(arr, m);//sorting the 2nd array
    for(in = 0; in < n; in++)
    {
        for(jn = 0; jn < m; jn++)
        {
            if(ar[in] * arr[jn] < p)
                nr++;
            else
                break;
        }
    }
    printf("%d", nr);
    return 0;
}

所以我必须阅读 ar[] 和 arr[] 以及 p。这是一个例子:

n = 5
p = 99
ar[5] = {1, 2, 3, 4, 5}
m = 2
arr[2] = {34, 25}

程序将打印 5，因为 1 * 34 < 99、1 * 25 < 99、2 * 34 < 99、2 * 25 < 99、3 * 25 < 99。

Answer 1

我假设元素是正的。

1. 使用快速排序方法(例如库 qsort())对两个数组进行排序。时间复杂度是O(nlogn+mlogm)
2. 假设您用乘法结果填充二维表。请注意，每一行和每一列都已排序。
3. 使用二进制搜索(或数字本身，如果存在)在该虚构矩阵的周边为 given number 找到一个位置。 O(log(n)+log(m))
4. 遍历矩阵直到另一条边，将较大的值与较小的值分开并计算它们。 O(n+m)

请注意，您不应该计算所有矩阵项(以避免二次复杂度)，只计算需要的项!

这是一种描述的算法here和 here (看极品图)