c - 如何减少执行时间？我应该使用函数还是保留嵌套循环的想法

Question

我必须减少这段代码的执行时间。在这个问题中，n 的值可能高达 10^8 。因此我认为嵌套循环不是那么好，因为它对于大数据来说非常滞后。所以我想知道是否使用函数而不是内循环。这个想法可以减少执行时间吗？或者即使我使用函数也会出现相同的情况？？

#include <stdio.h>
long long a[500001]={0};
int main()
{
long long n,i,j,flag,sum=0,temp,count=0;

scanf("%lld",&n);
for(i=0;i<n;i++)
    scanf("%lld",&a[i]);
for(i=0;i<n;i++){
    for(j=0;j<n;j++)
    if(a[j]>=a[i])
        count++;
     flag=a[i]*(count);
     if(flag>sum)
        sum=flag;
     count=0;
}
printf("%lld",sum);
return 0;
}

Answer 1

我认为你的问题是算法:

for(i=0;i<n;i++){
for(j=0;j<n;j++)

这里的复杂度为 O(n^2)，所以这是一个非常复杂的算法。

您能解释一下您希望通过该代码得到什么吗？

改进的解决方案

1) sort your data从较高值到较低值 O(n) 或 O(n*log(n))
2)使用这个算法:

 int max=0,tmp=0;
 for(i=0;i<n;i++){
      tmp=array[i]*(i+1);
      if(max<tmp) max=tmp;
  }

示例

输入:4 30 20 53 14

1) 数组 = {53,30,20,14,4}
2)

    tmp     | max | iteration  
    0       |0    | 0  
    53      |53   | 1  
  30*2=60   |60   | 2  
  20*3=60   |60   | 3  
  14*4=56   |60   | 4  
  4*5=20    |60   | 5  

输出:60

复杂性

如果排序是 O(nlog(n)) 并且我的算法是 O(n)，那么你会得到 O(nlog(n)) 复杂度。