1楼：把问题给我
比如for (int i=1;i 循环log2(n)次 根据log换底公式 最终复杂度写成ο(log(n)) 快速排序的时间复杂度为n*log n,请教一下n是代表什么，麻烦讲通俗一点，不要百度照搬 2楼：90李鹏 不知道你的数学基础如何，我简单描述一下。 前提定义 待数组的元素个数为n 背景介绍 何为快速排序？是否写过快速排序的**？至少这个你需要事先有所知道，要不然也仅仅是停留在记忆的层面，而不理解它为n*lgn的原因。 快速排序算法： 主要分为以下三个部分 1，partittion 2，quicksort前一部分 3，quicksort后一部分 简单说来就是，partition从要排序的数组中选取一个枢纽，例如即为pivot，然后将数组中比pivot小的元素放到它的左边，将比pivot大的元素放到它的右边（如果是递增排序的话）。因此根据时间复杂度的概念，这个partition的时间复杂度为n，这里的n就是你partition方法处理的数据长度。 为何partition的时间复杂度为n？ 看你的问题，既然问到了n，我就解释一下partition为什么会是n的时间复杂度。paritition方法选取枢纽，这个一般拿数组元素的第一个即可，这个不需要任何的循环操作，直接取值即可，换句话说这个时间复杂度是1，然后需要遍历数组，将比pivot大的元素放到右边，比pivot小的元素放到左边，这个至少要遍历整个数组，然后对每一个元素进行操作决定是否移动，处理一个元素的时间复杂度为1，现在有n个元素要处理，故而parition方法的时间复杂度为n。 为何快速排序的时间复杂度为n*lgn? 根据背景介绍中的算法描述，可以写出如下的递推公式： f(n) = 2 * f(n/2) + n 对上述函数进行解释如下： f(n)代表对n个元素进行排序处理所花费的时间（当然只是一个抽象的时间概念） 根据算法描述的三步，第一步partition就是等式右边的n，第二步和第三步中的quicksort就是等式右边的2 * f(n/2)。为什么是n/2 ? 这个应该很容易理解，partition将数组分成两部分，下面的quicksort分别排序前一部分和后一部分，此处我们假设这个拆分是完全等分的，也就是说前一部分和后一部分都是n/2。 对上述等式进行时间复杂度的运算如下： f(n) = 2 * f(n/2) + n = 2 * ( 2 * f(n/4) + n/2 ) + n = 4 * f(n/4) + 2 * n 希望你能看出这个推导，就是直接的代入而已，下面我不再继续了，可以看出每一次它等式右边就多出了一个n， 由于每次操作是进行除以2的操作，故而最多进行lgn，也就是说最终的运算结果： f(n) = k* f(1) + lgn*n。 好了，啰啰嗦嗦. 归并排序的时间复杂度o(n*log n)是怎么得来的，求大神详细的讲解一下
30 3楼：碧血玉叶花 首先你说归并排序最坏的情形为o(nlogn)，这是不正确的归并排序如果不借助辅助空间的话，复杂度为o(n^2)，借助的话就是o(nlogn)(o(nlog2n))归并排序 平均复杂度是 o(nlogn) 比较快 快速排序快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。 一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是o(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。 所以随机化快速排序可以对于绝大多数输入数据达到o(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。 ”随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到o(n^2)。解决方法是用一种方法进行扫描，使没有交换的情况下主元保留在原位置。 综合来说快速排序速度最快，时间复杂度最小。希望对你有所帮助！ 4楼：汗涤袁希月 搜一下：归并排序的时间复杂度o(n*log n)是怎么得来的，求大神详细的讲解一下 5楼：兔子s岁月 首先，你要理解两个长度为n/2的的数组做归并，这个时间复杂度是o(n)。 然后，因为归并排序要不断的把原来数组分成两份，这个递归的过程是o(logn)。比如说你想要排序的数组长度为8，然后不断一的一分为二，就是8——>4——>2——>1。一共拆了3次，2^3 = 8，或者3是以二为底的8的对数。 log就是这样来的。 然后两个再相乘，时间复杂度了就是o(nlogn)了。 时间复杂度log是怎么计算出的， 6楼：匿名用户 i每循环一次就乘了2，知道当i＞=n时循环结束，循环m次有2^m＞=n，得到m=log2n。 7楼：匿名用户 时间复杂度 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 1、时间复杂度 （1）时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。 一个算法中的语句执行次数称为语句频度或时间频度。记为t(n)。 （2）时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度t(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用t(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，t（n)/f(n)的极限值为不等于零的常数，则称f(n)是t(n)的同数量级函数。记作t(n)=o(f(n)),称o(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。 在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为o(1),另外，在时间频度不相同时，时间复杂度有可能相同，如t(n)=n2+3n+4与t(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为o(n2)。 按数量级递增排列，常见的时间复杂度有： 常数阶o(1),对数阶o(log2n),线性阶o(n), 线性对数阶o(nlog2n),平方阶o(n2)，立方阶o(n3),...， k次方阶o(nk),指数阶o(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 2、空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: s(n)=o(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。 递归算法和非递归算法在分析时间复杂度和空间复杂度上为什么不同 8楼：奔跑的窝牛的家 在算法分析中，当一个算法中包含递归调用时，其时间复杂度的分析会转化为一个递归方程求解。实际上，这个问题是数学上求解渐近阶的问题，而递归方程的形式多种多样，其求解方法也是不一而足，比较常用的有以下四种方法： (1)代入法(substitution method) 代入法的基本步骤是先推测递归方程的显式解，然后用数学归纳法来验证该解是否合理。 (2)迭代法(iteration method) 迭代法的基本步骤是迭代地递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。 (3)套用公式法(master method) 这个方法针对形如“t(n) = at(n/b) + f(n)”的递归方程。这种递归方程是分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子问题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。 (4)差分方程法(difference formula method) 可以将某些递归方程看成差分方程，通过解差分方程的方法来解递归方程，然后对解作出渐近阶估计。 下面就以上方法给出一些例子说明。 一、代入法 大整数乘法计算时间的递归方程为：t(n) = 4t(n/2) + o(n)，其中t(1) = o(1)，我们猜测一个解t(n) = o(n2 )，根据符号o的定义，对n>n0，有t(n) < **2 - eo(2n)（注意，这里减去o(2n)，因其是低阶项，不会影响到n足够大时的渐近性），把这个解代入递归方程，得到： t(n) = 4t(n/2) + o(n) ≤ 4c(n/2)2 - eo(2n/2)) + o(n) = **2 - eo(n) + o(n) ≤ **2 其中，c为正常数，e取1，上式符合 t(n)≤**2 的定义，则可认为o(n2 )是t(n)的一个解，再用数学归纳法加以证明。 二、迭代法 某算法的计算时间为：t(n) = 3t(n/4) + o(n)，其中t(1) = o(1)，迭代两次可将右端为： t(n) = 3t(n/4) + o(n) = o(n) + 3( o(n/4) + 3t(n/42 ) ) = o(n) + 3( o(n/4) + 3( o(n/42 ) + 3t(n/43 ) ) ) 从上式可以看出，这是一个递归方程，我们可以写出迭代i次后的方程： t(n) = o(n) + 3( o(n/4) + 3( o(n/42 ) + ... + 3( n/4i + 3t(n/4i+1 ) ) ) ) 当n/4i+1 =1时，t(n/4i+1 )=1，则 t(n) = n + (3/4) + (32 /42 )n + ... + (3i /4i )n + (3i+1 )t(1) < 4n + 3i+1 而由n/4i+1 =1可知，i0，有f(n) = o(nlogb a-ε )，则t(n) = o(nlogb a ) 2.若f(n) = o(nlogb a )，则t(n) = o(nlogb a *logn) 3.若f(n) = o(nlogb a+ε )，且对于某常数c>1和所有充分大的正整数n，有af(n/b)≤cf(n)，则t(n)=o(f(n))。 设t(n) = 4t(n/2) + n，则a = 4，b = 2，f(n) = n，计算得出nlogb a = nlog2 4 = n2 ，而f(n) = n = o(n2-ε )，此时ε= 1，根据第1种情况，我们得到t(n) = o(n2 )。 这里涉及的三类情况，都是拿f(n)与nlogb a 作比较，而递归方程解的渐近阶由这两个函数中的较大者决定。在第一类情况下，函数nlogb a 较大，则t(n)=o(nlogb a )；在第三类情况下，函数f(n)较大，则t(n)=o(f (n))；在第二类情况下，两个函数一样大，则t(n)=o(nlogb a *logn)，即以n的对数作为因子乘上f(n)与t(n)的同阶。 但上述三类情况并没有覆盖所有可能的f(n)。在第一类情况和第二类情况之间有一个间隙：f(n)小于但不是多项式地小于nlogb a ，第二类与第三类之间也存在这种情况，此时公式法不适用。 1楼 二分归并排序是一种分治算法 主定理方法 符合主定理 case 2 动动你的小手点个赞。 2楼 伟大的小天同学 o nlogn 和o nlog2n 是一样的。。归并排序如果不借助辅助空间的话，复杂度为o n 2 ，借助的话就是o nlogn o nlog2n 3楼 o n 以2为底的n的对数 。... 1楼 影墨者 o n for i 0 i 100 i o n 2 for i 0 i 100 i for j 0 j 100 j 算法时间复杂度o 1 和o 2 的区别？？？ 2楼 a罗网天下 o后面的括号中有一个函数，指明某个算法的耗时 耗空间与数据增长量之间的关系。其中的n代表输入数据的量。 时... 1楼 匿名用户 1 时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间...归并排序的时间复杂度是多少,归并排序的时间复杂度O是怎么算出来的呢
列举时间复杂度为O(n)和O(n2)的算法
数据结构算法时间复杂度定义,数据结构与算法，请问时间复杂度是怎么判定的？