c - 降低时间复杂度

Question

问的问题是用

struct match_score
{
char country[20];
int score;
};

其中结构与击球手的得分和他得分的国家有关。我们必须找到他的平均水平最高的国家/地区。

我写了一个时间复杂度为O(n^2)的代码谁能建议我如何将时间复杂度降低到 O(nlogn) 或 O(n)

复杂度为 O(n^2) 的代码

#include <stdio.h>
#include <string.h>
struct match_score
{ 
  char country[20];
  int score;
};
char *func(struct match_score *array,int len); 
main()
{
    struct match_score scores[]={
        {"Pakistan",23},
        {"India",52},
        {"Pakistan",40},
        {"India",22},
        {"Australia",80}
    };
    char *max_avg=func(scores,5);
    printf("%s",max_avg);

}
char *func(struct match_score *array,int len)
{

 int i,j,average[20],avg,l,max=0,max_num;
 char co[20];
 for(i=0;i<len;i++)
 {
     average[i]=0;
 }
 for(i=0;i<len;i++)
 {
      avg=0;
      l=0;
      strcpy(co,"");
      strcpy(co,array[i].country);
      for(j=0;j<len;j++)
      {
          if(strcmp(array[j].country,co)==0)
          {
              l++;
              avg+=array[j].score;
          } 
      }
      average[i]=avg/l;
   }

   for(i=0;i<len;i++)
   {
      if(average[i]>max)
      {
         max=average[i];
         max_num=i;
      }
   }
   for(i=0;i<len;i++)
   {
      printf("%d %d\n",i,average[i]);
   }
   return array[max_num].country;
}

Answer 1

你打n^2的区域就在这里；

 for(i=0;i<len;i++)
 {
      for(j=0;j<len;j++)
      {
          if(strcmp(array[j].country,co)==0)

所有这一切都是在您的数组中搜索重复的国家。如果以 n log n 的成本对数组进行排序，则可以找到 n 次序的重复项。这给你留下了一个新的复杂度 o(n log n)