这些是百度笔试题
3. 相似度计算用于衡量对象之间的相似程度,在数据挖据,自然语言处理中使一个基础性计算,在广告检索服务中往往也会判断网民检索Query和广告Adword 的主题相似度。假设Query 或者Adword 的主题属性定义为一个长度为10000 的浮点数据Pr[10000](称之为主题概率数组),其中Pr[i]表示Query 或者Adword 属于主题Id 为i 的概率,而Query和Adword 的相似度简化定义为两者主题概率数组的内积,即sim(Query,Adword)=sum(QueryPr[i]*AdwordPr[i])(0<==i<10000).在实际应用场景中,由于大多数主题的概率都为0,所以主题概率数组往往比较稀疏,在实现时会以一个紧凑型数组topic_info_t[]的方式保存,其中100<=数组大小<=1000,并按照topic_id 递增排列,
0<=topic_id<10000,0< topic_pr<1,
Struct topic_info_t {
int topic_id;
float topic_pr;
} ;
现在给出Query 的topic_info_t 数组和N(N>=5000)个Adwords 的topic_info_t 数组,现要求出Query 与Adwords 的相似度最大值,即
max(sim(Query,Adword[i])(0<=i<N).
float max_sim(const vector<topic_info_t>& query_topic_info,
const vector<topic_info_t> adwords_topic_info[],
int adwords_number);
编写代码求时间复杂度最低的算法,并给出时间复杂度分析。 |