大o的复杂度问题

《大o的复杂度问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、大0符号的最简单定义如下：---英文出处：stackoverflow大0待号是一种算法复杂度的相对表示方式。这个句子里有一些重要而严谨的用词：•相对（relative）:你只能比较相同的事物。你不能把一个做算数乘法的算法和排序整数列表的算法进行比较。但是，比较2个算法所做的算术操作（一个做乘法，一个做加法）将会告诉你一些有意义的东西；•表示（representation）大0（用它最简单的形式肥算法间的比较简化为了一个单一变量。这个变量的选择基于观察或假设。例如，fih序算法之间的对比通常是基于t匕较操作（比较2个结点来决定这2个结点的相对顺序）。这里面就假设了比较

2、操作的计算开销很大。但是，如果比较操作的计算开销不大，而交换操作的计算开销很大，又会怎么样呢？这就改变了先前的比较方式；•复杂度（complexity）:如果排序10,000个元素花费了我1秒，那么排序1百万个元素会花多少时间？在这个例子里，复杂度就是相对其他东西的度量结果。在你阅读了本文剩余部分后，再回来重读上面的文字吧。我所能想到的大0符号最好的例子就是做算术。拿两个数字（123456和789012）举例。我们在学校里学到的基本算术操作是：•加法；减法；•乘法;•除法。它们中每一个都是一次操作或一个问题。为它们求解的方法就被叫做算法(algorithm)o加法是

3、最简单的了。你把加数排成行，按列加上每个数字，把所加得的数的末位数字写到结果里。所加得的数的十位及其以上的数字转入下一列的计算中。让我们假设在算法中，加上这些数是计算开销最大的操作。合乎情理的说，为了把这两个数加起来我们必须要加6次数字(并且可能进位到第7次)。如果我们把两个100位数相加，我们必须做100次加法操作。如果我们把两个10,000位数相加，我们必须做10,000次加法操作。看到这里的模式了吗？复杂度(complexity,就是操作的数量)，对于加法中较大数的数字个数n,是直接成比例的。我们称这为0(n)或者线性复杂度(linearcomplexity)

4、o除了借位替代了进位，减法也是相似的。乘法就不同了。你把乘数排成行，取放在下面的乘数的第1个数字，把它逆序乘以上面乘数的每一个数字。下面乘数的其余数字也这样做。所以为了乘我们的两个6位数乘数,我们必须做36次乘法操作。我们还需要做10或11次列的加法操作来得到最终结果。如果我们有两个100位数相乘，我们需要做10,000次乘法操作和200次加法操作。两个100万位数相乘，我们需要做1万亿(1012)次乘法操作和200万次加法操作。作为n平方的算法衡量尺度，这就是O(n2),即平方复杂度(quadraticcomplexity)。现在是时候介绍另一个重要概念了：我们只

5、关心复杂度最重要的部分。敏锐的人可能已意识到，我们可以把操作次数表示为：n2+2n。但正如你所看到的，我们的两个100万位数相乘的例子，第二个2n无关紧要(在那个阶段，2n只占操作总量的0.0002%)。有人注意到我们在这里假设场景为最坏的情况。当我们做6位数乘法时，如果其中一个是4位数另一个是6位数，那么我们只需做24次乘法操作。然而，对于那个’n',我们仍然计算最坏情况，即乘数都是6位数的情况。因此，大0符号是关于一个算法的最坏情况的。电话簿我所能想到的下一个最棒的例子就是电话簿，通常叫做白页电话簿或者其它类似名字，因国而异。但我要谈论的是这种电话薄，这种电话薄

6、把人按这样的顺序排列：姓、缩写或名、地址、然后是电话号码。VIPDiariesTelephoneBook现在如果你要指示计算机在一个包含1,000,000个名字的电话簿中查找"」ohnSmith"的电话号码，你会怎么做？忽略也许你能猜测出S从电话簿哪里开始的事实(假设你不能猜测)，你会怎么做？一种典型的实现也许是，打开电话簿的正中间，取第500,000条记录，把它和"Smith"进行比较。如果这恰好就是"Smith,john",那我们真幸运。然而，"JohnSmith"更有可能在其前面或后面。如果在后面，那么我们把电话簿后面一半从中间划分开，然后重复之前的过程；如果

7、在前面，那么我们把第一半从中间划分开，然后重复之前的过程。以此类推。这种算法叫做二分搜索(binarysearch)。不论你是否意识到，它在编程中每天都用到。因此，如果你想要在包含100万名字的电话簿中查找一个名字，事实上，通过这种算法，最多20次，你能找到任何名字。在比较搜索算法中，我们决定把比较操作作为我们的’rf。对于有3个名字的电话簿，最多需2次比较。•对于有7个名字的电话簿，最多需3次比较。•对于有15个名字的电话簿，最多需4次比较。•...•对于有1,000,000个名字的电话簿，最多需20次比较。这简直好得难以置信，不是吗？用大O术语就是O(log