下述算法的时间发杂度Tn

‘壹’ 某算法的时间复杂度为O(n),表明该算法的：

C、执行时间与n成正比。

A选项，算法的时间复杂度与问题规模没有任何关系。故A选项错误。

B选项，任何算法的执行时间都几乎不可能完全等于。故B选项错误。

C选项，如果一个算法的时间复杂度为，的值增加，的值也会随之增加，那么执行时间肯定就是与成正比的。故C选项正确。

D选项，一个算法的时间复杂度与这个问题的数据规模没有关系，故D选项也错误。

(1)下述算法的时间发杂度Tn扩展阅读：

算法的时间复杂度通常用大O符号表述，定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。

如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。

‘贰’ 确定下列算法中语句的执行次数，并给出算法的时间复杂度

int n=10,cout=0; 执行1次 ,时间复杂度Tn=O(1),
for(int i=1;i<=n;i++) 执行（n+1）次，原操作时间复杂度Tn=O(n) ，
for(int j=1;j<=i;j++) 执行1+2+3+...+n=1/2(n²+n)次， 原操作时间复杂度Tn=O(n²) ,
for(int k=1;k<=j;k++) 执行1+(1+2)+(1+2+3)+...+[1/2(n²+n)]=1/6(n³+3n²+2n)次，n的最高次幂是3，原操作时间复杂度Tn=O(n³)，
cout ++;（原操作） 执行1+(1+2)+(1+2+3)+...+[1/2(n²+n)]=1/6(n³+3n²+2n)次，原操作时间复杂度Tn=O(n³)

‘叁’ 绠楁硶镄勫嶆潅搴︿富瑕佸寘𨰾

绠楁硶镄勫嶆潅搴︿富瑕佸寘𨰾镞堕棿澶嶆潅搴﹀拰绌洪棿澶嶆潅搴︺

绠楁硶镄勬椂闂村嶆潅搴﹀拰绌洪棿澶嶆潅搴﹀悎绉颁负绠楁硶镄勫嶆潅搴︺

镞堕棿澶嶆潅搴︼细镞堕棿澶嶆潅搴︽槸鎸囨墽琛岀畻娉曟墍闇瑕佺殑璁＄畻宸ヤ綔閲忋

绌洪棿澶嶆潅搴︼细鏄瀵逛竴涓绠楁硶鍦ㄨ繍琛岃繃绋嬩腑涓存椂鍗犵敤瀛桦偍绌洪棿澶у皬镄勯噺搴︺

绠楁硶镄勫嶆潅镐т綋杩愯岃ョ畻娉曟椂镄勮＄畻链烘墍闇璧勬簮镄勫氩皯涓婏纴璁＄畻链鸿祫婧愭渶閲嶈佺殑鏄镞堕棿鍜岀┖闂达纸鍗冲瘎瀛桦櫒锛夎祫婧愶纴锲犳ゅ嶆潅搴﹀垎涓烘椂闂村拰绌洪棿澶嶆潅搴︺

澶嶆潅搴﹀垎鏋愶细

阃氩父涓涓绠楁硶镄勫嶆潅搴︽槸鐢卞叾杈揿叆閲忓喅瀹氱殑锛岄殢镌杈揿叆镄勫炲姞锛屼笉钖岀畻娉旷殑澶嶆潅搴﹀为暱阃熷害涓轰简闄崭绠绠楁硶澶嶆潅搴︼纴搴斿綋钖屾椂钥冭槛鍒拌緭鍏ラ噺锛岃捐¤缉濂界殑绠楁硶銆

钖屼竴闂棰桦彲鐢ㄤ笉钖岀畻娉曡В鍐筹纴钥屼竴涓绠楁硶镄勮川閲忎紭锷ｅ皢褰卞搷鍒扮畻娉曚箖镊崇▼搴忕殑鏁堢巼銆傜畻娉曞垎鏋愮殑鐩镄勫湪浜庨夋嫨钖堥傜畻娉曞拰鏀硅繘绠楁硶銆备竴涓绠楁硶镄勮瘎浠蜂富瑕佷粠镞堕棿澶嶆潅搴﹀拰绌洪棿澶嶆潅搴︽潵钥冭槛銆

‘肆’ 算法的时间复杂度取决于什么

算法的时间复杂度取决于问题的规模，待处理数据的初态。

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中基本运算（最深层循环内的语句）的频度与Tn)同数量级，因此通常采用算法中基本运算的频度fn)来分析算法的时间复杂度3。

算法的时间复杂度记为：T(n)= O(fn))式中，О 的含义是T(n)的数量级，其严格的数学定义是:若T(n)和fn)是定义在正整数集合上的两个函数，则存在正常数C和n，使得当n≥no时，都满足0≤T(n)≤Cfn)。

算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质（如输入数据元素的初始状态)。

‘伍’ 一道经典的面试题：如何从N个数中选出最大（小）的n个数

这个问题我前前后后考虑了有快一年了，也和不少人讨论过。据我得到的消息，Google和微软都面过这道题。这道题可能很多人都听说过，或者知道答案（所谓的堆），不过我想把我的答案写出来。我的分析也许存有漏洞，以交流为目的。但这是一个满复杂的问题，蛮有趣的。看完本文，也许会启发你一些没有想过的解决方案（我一直认为堆也许不是最高效的算法）。在本文中，将会一直以寻找n个最大的数为分析例子，以便统一。注：本文写得会比较细节一些，以便于绝大多数人都能看懂，别嫌我罗嗦:) 我很不确定多少人有耐心看完本文！ Naive 方法： 首先，我们假设n和N都是内存可容纳的，也就是说N个数可以一次load到内存里存放在数组里（如果非要存在链表估计又是另一个challenging的问题了）。从最简单的情况开始，如果n=1，那么没有任何疑惑，必须要进行N-1次的比较才能得到最大的那个数，直接遍历N个数就可以了。如果n=2呢？当然，可以直接遍历2遍N数组，第一遍得到最大数max1，但是在遍历第二遍求第二大数max2的时候，每次都要判断从N所取的元素的下标不等于max1的下标，这样会大大增加比较次数。对此有一个解决办法，可以以max1为分割点将N数组分成前后两部分，然后分别遍历这两部分得到两个最大数，然后二者取一得到max2。 也可以遍历一遍就解决此问题，首先维护两个元素max1，max2（max1=max2），取到N中的一个数以后，先和max1比，如果比max1大（则肯定比max2大），直接替换max1，否则再和max2比较确定是否替换max2。采用类似的方法，对于n=2，3，4一样可以处理。这样的算法时间复杂度为O（nN）。当n越来越大的时候（不可能超过N/2，否则可以变成是找N-n个最小的数的对偶问题），这个算法的效率会越来越差。但是在n比较小的时候（具体多小不好说），这个算法由于简单，不存在递归调用等系统损耗，实际效率应该很不错. 堆：当n较大的时候采用什么算法呢？首先我们分析上面的算法，当从N中取出一个新的数m的时候，它需要依次和max1，max2，max3max n比较，一直找到一个比m小的max x，就用m来替换max x，平均比较次数是n/2。可不可以用更少的比较次数来实现替换呢？最直观的方法是，也就是网上文章比较推崇的堆。堆有这么一些好处：1.它是一个完全二叉树，树的深度是相同节点的二叉树中最少的，维护效率较高；2.它可以通过数组来实现，而且父节点p与左右子节l，r点的数组下标的关系是s[l] = 2*s[p]+1和s[r] = 2*s[p]+2。在计算机中2*s[p]这样的运算可以用一个左移1位操作来实现，十分高效。再加上数组可以随机存取，效率也很高。3.堆的Extract操作，也就是将堆顶拿走并重新维护堆的时间复杂度是O（logn），这里n是堆的大小。 具体到我们的问题，如何具体实现呢？首先开辟一个大小为n的数组区A，从N中读入n个数填入到A中，然后将A维护成一个小顶堆（即堆顶A[0]中存放的是A中最小的数）。然后从N中取出下一个数，即第n+1个数m，将m与堆顶A[0]比较，如果m<=A[0]，直接丢弃m。否则应该用m替换A[0]。但此时A的堆特性可能已被破坏，应该重新维护堆：从A[0]开始，将A[0]与左右子节点分别比较（特别注意，这里需要比较两次才能确定最大数，在后面我会根据这个来和败者树比较），如果A[0]比左右子节点都小，则堆特性能够保证，勿需继续，否则如左（右）节点最大，则将A[0]与左（右）节点交换，并继续维护左（右）子树。依次执行，直到遍历完N，堆中保留的n个数就是N中最大的n个数。 这都是堆排序的基本知识，唯一的trick就是维护一个小顶堆，而不是大顶堆。不明白的稍微想一下。维护一次堆的时间复杂度为O（logn），总体的复杂度是O（Nlogn）这样一来，比起上面的O（nN），当n足够大时，堆的效率肯定是要高一些的。当然，直接对N数组建堆，然后提取n次堆顶就能得到结果，而且其复杂度是O（nlogN）,当n不是特别小的时候这样会快很多。但是对于online数据就没办法了，比如N不能一次load进内存，甚至是一个流，根本不知道N是多少。 败者树：有没有别的算法呢？我先来说一说败者树（loser tree）。也许有些人对loser tree不是很了解，其实它是一个比较经典的外部排序方法，也就是有x个已经排序好的文件，将其归并为一个有序序列。败者树的思想咋一看有些绕，其实是为了减小比较次数。首先简单介绍一下败者树：败者树的叶子节点是数据节点，然后两两分组（如果节点总数不是2的幂，可以用类似完全树的结构构成树），内部节点用来记录左右子树的优胜者中的败者（注意记录的是输的那一方），而优胜者则往上传递继续比较，一直到根节点。如果我们的优胜者是两个数中较小的数，则根节点记录的是最后一次比较中的败者，也就是所有叶子节点中第二小的那个数，而最小的那个数记录在一个独立的变量中。这里要注意，内部节点不但要记录败者的数值，还要记录对应的叶子节点。如果是用链表构成的树，则内部节点需要有指针指向叶子节点。这里可以有一个trick，就是内部节点只记录败者对应的叶子节点，具体的数值可以在需要的时候间接访问（这一方法在用数组来实现败者树时十分有用，后面我会讲到）。关键的来了，当把最小值输出后，最小值所对应的叶子节点需要变成一个新的数（或者改为无穷大，在文件归并的时候表示文件已读完）。接下来维护败者树，从更新的叶子节点网上，依次与内部节点比较，将败者更新，胜者往上继续比较。由于更新节点占用的是之前的最小值的叶子节点，它往上一直到根节点的路径与之前的最小值的路径是完全相同的。内部节点记录的败者虽然称为败者，但却是其所在子树中最小的数。也就是说，只要与败者比较得到的胜者，就是该子树中最小的那个数（这里讲得有点绕了，看不明白的还是找本书看吧，对照着图比较容易理解）。 注：也可以直接对N构建败者树，但是败者树用数组实现时不能像堆一样进行增量维护，当叶子节点的个数变动时需要完全重新构建整棵树。为了方便比较堆和败者树的性能，后面的分析都是对n个数构建的堆和败者树来分析的。 总而言之，败者树在进行维护的时候，比较次数是logn+1。与堆不同的是，败者树是从下往上维护，每上一层，只需要和败者节点比较一次即可。而堆在维护的时候是从上往下，每下一层，需要和左右子节点都比较，需要比较两次。从这个角度，败者树比堆更优一些。但是，请注意但是，败者树每一次维护必定需要从叶子节点一直走到根节点，不可能中间停止；而堆维护时，有可能会在中间的某个层停止，不需要继续往下。这样一来，虽然每一层败者树需要的比较次数比堆少一倍，但是走的层数堆会比败者树少。具体少多少，从平均意义上到底哪一个的效率会更好一些？那我就不知道了，这个分析起来有点麻烦。感兴趣的人可以尝试一下，讨论讨论。但是至少说明了，也许堆并非是最优的。 具体到我们的问题。类似的方法，先构建一棵有n个叶子节点的败者树，胜出者w是n个中最小的那一个。从N中读入一个新的数m后，和w比较，如果比w小，直接丢弃，否则用m替换w所在的叶子节点的值，然后维护该败者树。依次执行，直到遍历完N，败者树中保留的n个数就是N中最大的n个数。时间复杂度也是O（Nlogn） 类快速排序方法： 快速排序大家大家都不陌生了。主要思想是找一个轴节点，将数列交换变成两部分，一部分全都小于等于轴，另一部分全都大于等于轴，然后对两部分递归处理。其平均时间复杂度是O（NlogN）。从中可以受到启发，如果我们选择的轴使得交换完的较大那一部分的数的个数j正好是n，不也就完成了在N个数中寻找n个最大的数的任务吗？当然，轴也许不能选得这么恰好。可以这么分析，如果jn，则最大的n个数肯定在这j个数中，则问题变成在这j个数中找出n个最大的数；否则如果j<n，则这j个数肯定是n个最大的数的一部分，而剩下的j-n个数在小于等于轴的那一部分中，同样可递归处理。 需要注意的是，这里的时间复杂度是平均意义上的，在最坏情况下，每次分割都分割成1：N-2，这种情况下的时间复杂度为O（n）。但是我们还有杀手锏，可以有一个在最坏情况下时间复杂度为O（N）的算法，这个算法是在分割数列的时候保证会按照比较均匀的比例分割，at least 3n/10-6。具体细节我就不再说了，感兴趣的人参考算法导论（Introction to Algorithms 第二版第九章 Medians and Orders Statistics）。 还是那个结论，堆不见得会是最优的。 本文快要结束了，但是还有一个问题：如果N非常大，存放在磁盘上，不能一次装载进内存呢？怎么办？对于介绍的Naive方法，堆，败者树等等，依然适用，需要注意的就是每次从磁盘上尽量多读一些数到内存区，然后处理完之后再读入一批。减少IO次数，自然能够提高效率。而对于类快速排序方法，稍微要麻烦一些：分批读入，假设是M个数，然后从这M个数中选出n个最大的数缓存起来，直到所有的N个数都分批处理完之后，再将各批次缓存的n个数合并起来再进行一次类快速排序得到最终的n个最大的数就可以了。在运行过程中，如果缓存数太多，可以不断地将多个缓存合并，保留这些缓存中最大的n个数即可。由于类快速排序的时间复杂度是O（N），这样分批处理再合并的办法，依然有极大的可能会比堆和败者树更优。当然，在空间上会占用较多的内存。 总结：对于这个问题，我想了很多，但是觉得还有一些地方可以继续深挖：1. 堆和败者树到底哪一个更优？可以通过理论分析，也可以通过实验来比较。也许会有人觉得这个很无聊；2. 有没有近似的算法或者概率算法来解决这个问题？我对这方面实在不熟悉，如果有人有想法的话可以一块交流。如果有分析错误或遗漏的地方，请告知，我不怕丢人，呵呵！最后请时刻谨记，时间复杂度不等于实际的运行时间，一个常数因子很大的O（logN）算法也许会比常数因子小的O（N）算法慢很多。所以说，n和N的具体值，以及编程实现的质量，都会影响到实际效率。

‘陆’ 算法的时间复杂度是指什么

算法的时间复杂度是指：执行程序所需的时间。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近无穷大时。

T(n)/f(n)的极限值为不等于零的常数，则称为f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。比如：

在 T(n)=4nn-2n+2 中，就有f(n)=nn，使得T(n)/f(n)的极限值为4，那么O(f(n))，也就是时间复杂度为O(n*n)。

时间复杂度中大O阶推导是：

推导大O阶就是将算法的所有步骤转换为代数项，然后排除不会对问题的整体复杂度产生较大影响的较低阶常数和系数。

有条理的说，推导大O阶，按照下面的三个规则来推导，得到的结果就是大O表示法：运行时间中所有的加减法常数用常数1代替。只保留最高阶项去除最高项常数。

其他常见复杂度是：

f(n)=nlogn时，时间复杂度为O(nlogn)，可以称为nlogn阶。

f(n)=n³时，时间复杂度为O(n³)，可以称为立方阶。

f(n)=2ⁿ时，时间复杂度为O(2ⁿ)，可以称为指数阶。

f(n)=n!时，时间复杂度为O(n!)，可以称为阶乘阶。

f(n)=(√n时，时间复杂度为O(√n)，可以称为平方根阶。