Question

两道JAVA题目，求大神解答

实验一
1. 简述百度的搜索核心算法
2. 验证下列算法的时间复杂度
A..一个循环的时间复杂度为O(n)。
int n=10,sum=0;
for(int i=0;i<n;i++)
sum+=n;
B 时间复杂度为O(n2)的二重循环。
int n=9;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
System.out.print(i*j);
如果
int n=9;
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
System.out.print(i*j);
二重循环的执行次数为 ，时间复杂度仍为O(n2
C.时间复杂度为O(nlog2n)的二重循环。
int n=8;
for(int i=1;i<=n;i*=2)
for(int j=1;j<=n;j++)
System.out.print(i*j);
循环次数为 。时间复杂度为O(nlog2n)。

D.时间复杂度为O(n)的二重循环。
int n=8;
for(int i=1;i<=n;i*=2)
for(int j=1;j<=i;j++)
System.out.print(i*j);
总的循环次数为 。时间复杂度为O(n)

Answer 1

A、
循环执行n次，时间复杂度为O(n)。

B、
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
第一重循环每1次，第二重循环n次，第一重循环每共n次，所以这个循环总共n²次
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
这个循环总共执行1+2+...+n=(1+n)n/2次
总共循环n²+(1+n)n/2次，时间复杂度为O(n²)。

C、
for(int i=1;i<=n;i*=2)
for(int j=1;j<=n;j++)
第一重循环每1次，第二重循环n次，第一重循环每共log2n次，所以这个循环总共nlog2n次，时间复杂度为O(nlog2n)。

D、
for(int i=1;i<=n;i*=2)
for(int j=1;j<=i;j++)
这个循环总共执行1+2+...+log2n=(1+log2n)log2n/2次，时间复杂度为O(n)

Answer 2

我们都知道百度号称"全球最大得中文搜索技术供给商"。中国所有供给搜索引擎得门户网站中，百度是全球最优秀得中文信息检索与传递技术供给商。其中可定制、高扩展性的调度算法使得搜索器能在极短得时间内采集到最大数目的互联网信息。
百度搜索引擎使用了高性能得"网络蜘蛛"程序自动得在互联网中搜索信息。百度搜索引擎拥有目前世界上最大得中文信息库，总量达到6000万页上面，并且还在以每天几十万页得速度快速增长。
由于百度后台运用了高效得信息索引算法，大大提高了检索时得响应速度和承受大网站流量时得稳定性，相应的作为搜索引擎的谷歌也是，可是我们怎么知道这些搜索引擎是怎么计算这些信息并采集到给需要的人的呢？作为seoer初学者，我查找了先关的信息，算法很多，核心的大致分一下3点：

Hilltop算法

是由Krishna Baharat在2000年左右所研究的，于2001年申请了专利，并且把专利授权给Google使用，后来Krishna Baharat本人也加入了Google。
Hilltop算法可以简单理解为与主题相关的PR值。传统PR值与特定关键词或主题没有关联，只计算链接关系。这就有可能出现某种漏洞。比如一个PR值极高的关于环保内容的大学页面，上面有一个链接连向一个儿童用品网站，这个链接出现的原因可能仅仅是因为这个大学页面维护人是个教授，他太太在那个卖儿童用品的公司工作。这种与主题无关、却有着极高PR值的链接，有可能使一些网站获得很好的排名，但其实相关性并不高。
Hilltop算法就尝试矫正这种可能出现的疏漏。Hilltop算法同样是计算链接关系，不过它更关注来自主题相关页面的链接权重。在Hilltop算法中把这种主题相关页面称为专家文件。显然，针对不同主题或搜索词有不同的专家文件。
根据Hilltop算法，用户搜索关键词后，Google先按正常排名算法找到一系列相关页面并排名，然后计算这些页面有多少来自专家文件的、与主题相关的链接，来自专家文件的链接越多，页面的排名分值越高。按Hilltop算法的最初构想，一个页面至少要有两个来自专家文件的链接，才能返回一定的Hilltop值，不然返回的Hilltop值将为零。
根据专家文件链接计算的分值被称为LocalRank。排名程序根据LocalRank值，对原本传统排名算法计算的排名做重新调整，给出最后排名。这就是前面讨论的搜索引擎排名阶段最后的过滤和调整步骤。
Hilltop算法最初写论文和申请专利时对专家文件的选择有不同描述。在最初的研究中，Krishna Baharat把专家文件定义为包含特定主题内容，并且有比较多导出链接到第三方网站的页面，这有点类似于HITS算法中的枢纽页面。专家文件链接指向的页面与专家文件本身应该没有关联，这种关联指的是来自同一个主域名下的子域名，来自相同或相似IP地址的页面等。最常见的专家文件经常来自于学校、政府及行业组织网站。
在最初的Hilltop算法中，专家文件是预先挑选的。搜索引擎可以根据最常见的搜索词，预先计算出一套专家文件，用户搜索时，排名算法从事先计算的专家文件集合中选出与搜索词相关的专家文件子集，再从这个子集中的链接计算LocalRank值。
不过在2001年所申请的专利中，Krishna Baharat描述了另外一个挑选专家文件的方法，专家文件并不预先选择，用户搜索特定查询词后，搜索引擎按传统算法挑出一系列初始相关页面，这些页面就是专家文件。Hilltop算法在这个页面集合中再次计算哪些网页有来自于集合中其他页面的链接，赋予比较高的LocalRank值。由于传统算法得到的页面集合已经具备了相关性，这些页面再提供链接给某一个特定页面，这些链接的权重自然应该很高。这种挑选专家文件的方法是实时进行的。
通常认为Hilltop算法对2003年底的佛罗里达更新有重大影响，不过Hilltop算法是否真的已经被融入进Google排名算法中，没有人能够确定。Google从来没有承认、也没有否认自己的排名算法中是否使用了某项专利。不过从排名结果观察及招揽Krishna Baharat至麾下等迹象看，Hilltop算法的思想得到了Google的极大重视。
Hilltop算法提示SEO，建设外部链接时更应该关注主题相关的网站。最简单的方法是搜索某个关键词，目前排在前面的页面就是最好的链接来源，甚至可能一个来自竞争对手网站的链接效果是最好的。当然，获得这样的链接难度最大。

TrustRank算法

TrustRank是近年来比较受关注的基于链接关系的排名算法。TrustRank可以翻译为“信任指数”。
TrustRank算法最初来自于2004年斯坦福大学和雅虎的一项联合研究，用来检测垃圾网站，并且于2006年申请专利。TrustRank算法发明人还发表了一份专门的PDF文件，说明TrustRank算法的应用。
TrustRank算法并不是由Google提出的，不过由于Google所占市场份额最大，而且TrustRank在Google排名中也是一个非常重要的因素，所以有些人误以为TrustRank是Google提出的。更让人糊涂的是，Google曾经把TrustRank申请为商标，但是TrustRank商标中的TrustRank指的是Google检测含有恶意代码网站的方法，而不是指排名算法中的信任指数。
TrustRank算法基于一个基本假设：好的网站很少会链接到坏的网站。反之则不成立，也就是说，坏的网站很少链接到好网站这句话并不成立。正相反，很多垃圾网站会链接到高权威、高信任指数的网站，试图提高自己的信任指数。
基于这个假设，如果能挑选出可以百分之百信任的网站，这些网站的TrustRank评为最高，这些TrustRank最高的网站所链接到的网站信任指数稍微降低，但也会很高。与此类似，第二层被信任的网站链接出去的第三层网站，信任度继续下降。由于种种原因，好的网站也不可避免地会链接到一些垃圾网站，不过离第一层网站点击距离越近，所传递的信任指数越高，离第一级网站点击距离就越远，信任指数将依次下降。这样，通过TrustRank算法，就能给所有网站计算出相应的信任指数，离第一层网站越远，成为垃圾网站的可能性就越大。
计算TrustRank值首先要选择一批种子网站，然后人工查看网站，设定一个初始TrustRank值。挑选种子网站有两种方式，一种是选择导出链接最多的网站，因为TrustRank算法就是计算指数随着导出链接的衰减。导出链接多的网站，在某种意义上可以理解为“逆向PR值”比较高。
另一种挑选种子网站的方法是选PR值高的网站，因为PR值越高，在搜索结果页面出现的概率就越大。这些网站才正是TrustRank算法最关注的、需要调整排名的网站。那些PR值很低的页面，在没有TrustRank算法时排名也很靠后，计算TrustRank意义就不大了。
根据测算，挑选出两百个左右网站作为种子，就可以比较精确地计算出所有网站的TrustRank值。
计算TrustRank随链接关系减少的公式有两种方式。一种是随链接次数衰减，也就是说如果第一层页面TrustRank指数是100，第二层页面衰减为90，第三层衰减为80。第二种计算方法是按导出链接数目分配TrustRank值，也就是说，如果一个页面的TrustRank值是100，页面上有5个导出链接，每个链接将传递20%的TrustRank值。衰减和分配这两种计算方法通常综合使用，整体效果都是随着链接层次的增加，TrustRank值逐步降低。
得出网站和页面的TrustRank值后，可以通过两种方式影响排名。一种是把传统排名算法挑选出的多个页面，根据TrustRank值比较，重新做排名调整。另一种是设定一个最低的TrustRank值门槛，只有超过这个门槛的页面，才被认为有足够的质量进入排名，低于门槛的页面将被认为是垃圾页面，从搜索结果中过滤出去。
虽然TrustRank算法最初是作为检测垃圾的方法，但在现在的搜索引擎排名算法中，TrustRank概念使用更为广泛，常常影响大部分网站的整体排名。TrustRank算法最初针对的是页面级别，现在在搜索引擎算法中，TrustRank值也通常表现在域名级别，整个域名的信任指数越高，整体排名能力就越强。

HITS算法

HITS是英文Hyperlink-Induced Topic Search 的缩写，意译为“超链诱导主题搜索”。
按照HITS算法，用户输入关键词后，算法对返回的匹配页面计算两种值，一种是枢纽值（Hub Scores），另一种是权威值（Authority Scores），这两个值是互相依存、互相影响的。所谓枢纽值，指的是页面上所有导出链接指向页面的权威值之和。权威值指的是所有导入链接所在页面的枢纽值之和。
上面的定义比较拗口，我们可以简单地说，HITS算法会提炼出两种比较重要的页面，也就是枢纽页面和权威页面。枢纽页面本身可能没有多少导入链接，但是有很多导出链接指向权威页面。权威页面本身可能导出链接不多，但是有很多来自枢纽页面的导入链接。
典型的枢纽页面就是如雅虎目录、开放目录或好123这样的网站目录。这种高质量的网站目录作用就在于指向其他权威网站，所以称为枢纽。而权威页面有很多导入链接，其中包含很多来自枢纽页面的链接。权威页面通常是提供真正相关内容的页面。
HITS算法是针对特定查询词的，所以称为主题搜索。
HITS算法的最大缺点是，它在查询阶段进行计算，而不是在抓取或预处理阶段。所以HITS算法是以牺牲查询排名响应时间为代价的。也正因为如此，原始HITS算法在搜索引擎中并不常用。不过HITS算法的思想很可能融入到搜索引擎的索引阶段，也就是根据链接关系找出具有枢纽特征或权威特征的页面。
成为权威页面是第一优先，不过难度比较大，唯一的方法就是获得高质量链接。当你的网站不能成为权威页面时，就让它成为枢纽页面。所以导出链接也是当前搜索引擎排名因素之一。绝不链接到其他网站的做法，并不是好的SEO方法。
这些是多方面找到的资料，希望可以帮助大家多了解下，也有不全面的信息，希望多多指导！