减少时间复杂性

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)的新复杂性