0

问的问题是使用

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;
}
4

3 回答 3

7

你击中 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) 的新复杂度

于 2013-07-22T12:39:12.690 回答
1

您可以使用一个临时集合来存储平均值,然后对其进行迭代以找到最大的。这将使用更多空间,但将是 O(2n),因为您必须连续循环而不是嵌套。

于 2013-07-22T12:37:48.653 回答
-1

如果您对数组进行排序,您的复杂性会大大减少。在排序后的数组中搜索数字要快得多....

顺便说一句,您应该已经解释了您的算法和代码,或者至少给出了一些注释...

于 2013-07-22T12:45:33.283 回答