c - 如何提高以下代码的性能？

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

这个问题似乎与 help center 中定义的范围内的编程无关。 .

已关闭 3 年前。

Improve this question

这是问题。使用数组的值查找输入变量的最大 GCD。

输入如下:-第一行包含两个整数，N 和 Q。

第二行包含 N 个整数，组成 arr[]。

接下来，Q 行包含一个整数 M，即她希望返回的时间(以秒为单位)。

#include <stdio.h>

int main(){
    int n,q;
    scanf("%d %d", &n,&q);
    int a[n];
    int gcdn[n];
    for (int i = 0;i < n; i++) {
        scanf("%d",&a[i]);      }
    while (q>0){
        q--;
        int x;
        scanf("%d",&x);
        for(int i=0;i<n;i++) {
            gcdn[i] = gcd(a[i],x);
        }
        printf("%d \n",max(gcdn,n));
    }

}

int gcd (int a, int b) {
    if (b==0)
        return a;
    else 
        return gcd(b, a%b);
}
int max(int *a,int n) {
    int max= a[0];
    for(int i = 1;i<n;i++) {
        if(a[i]>min) {
            max= a[i];
        }
    }
    return max;
}

如何使这段代码在竞争性编程方面变得更好？还有哪些其他语言可以使这段代码更好、更高效？

Answer 1

最明显的性能改进是您的数组未排序:您需要首先进行搜索，而不是简单地向数组中添加元素(即 O(\log(n)))，但是一旦您需要获取数组的最大值，您只需要第一个(或最后一个)条目。