算法导论时间复杂度

㈠ 算法时间复杂度计算

首先假设任意一个简单运算的时间都是1，例如a=1;a++;a=a*b;这些运算的时间都是1.

那么例如
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
a++; //注意，这里计算一次的时间是1.
}
那么上面的这个例子的时间复杂度就是 m*n

再例如冒泡排序的时间复杂度是N*N；快排的时间复杂度是log(n)。

详细的情况，建议你看《算法导论》，里面有一章节，具体讲这个的。

㈡ 最优合并问题的时间复杂度怎么算

一般来说, 标准的分治法合并排序时间复杂度为O(n * lg n), 略小于插入排序的O(n*n), 递归式的时间复杂度求解方法比较多,有画图分析法, 算式求解即类似于 T(n) = f(T(n-1))的求解方法, 还有就是凭经验猜然后用数学归纳法证明等等, 对于你的问题最直观的方法就是画图法, 这是一个二叉树问题, 最开始的序列被递归地分为两份, 因此这棵树的高度为lg n的下取整(这里我们不讨论取整的细节), 层数为1 + lg n, 每一层的合并排序代价总和都为c*n(c为某个常数), 因此整棵树代价为c*n*lg n + c*n, 因此时间复杂度为O(n*lg n);
也可以用他的表达式求解,这个问题的表达式为:T(n)=2*T(n/2)+O(n)
严格来讲,上面所说的O更好的替代品为theta(符号打不出来,就用这个代替吧,^_^), 具体可以参考一下机械工业出版社的《算法导论》
参考资料： 机械工业出版社《算法导论》

㈢ 各种排序法的时间复杂度到底多少

根据《算法导论（中文版）》P83表格以及《算法（中文版）》部分章节内容：

算法最坏情况运行时间平均情况

冒泡&&插入&&选择排序 n^2n^2

快速排序n^2 n*log n

希尔排序（希尔增量） n^2 n^(1.3 - 2)

堆排序 n*log n n*log n

注：希尔排序的性能依赖于选择的增量。

㈣ 递归算法时间复杂度怎么分析

1、递归
是指对一个问题的求解，可以通过同一问题的更简单的形式的求解来表示. 并通过问题的简单形式的解求出复杂形式的解. 递归是解决一类问题的重要方法. 递归程序设计是程序设计中常用的一种方法，它可以解决所有有递归属性的问题，并且是行之有效的. 但对于递归程序运行的效率比较低，无论是时间还是空间都比非递归程序更费，若在程序中消除递归调用，则其运行时间可大为节省. 以下讨论递归的时间效率分析方法，以及与非递归设计的时间效率的比较.
2 时间复杂度的概念及其计算方法
算法是对特定问题求解步骤的一种描述. 对于算法的优劣有其评价准则，主要在于评价算法的时间效率，算法的时间通过该算法编写的程序在计算机中运行的时间来衡量，所花费的时间与算法的规模n有必然的联系，当问题的规模越来越大时，算法所需时间量的上升趋势就是要考虑的时间度量.
算法的时间度量是依据算法中最大语句频度（指算法中某条语句重复执行的次数）来估算的，它是问题规模n的某一个函数f(n). 算法时间度量记作：T（n）=O（f（n））
它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的时间复杂度，简称时间复杂度[2].
例如下列程序段：
（1）x=x+1;（2）for(i=1;i<=n;i++) x=x+1;（3）for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1. 以上三个程序段中，语句x=x+1的频度分别为1，n，n2，则这三段程序的时间复杂度分别为O（1），O（n），O（n2）.
求解过程为：先给出问题规模n的函数的表达式，然后给出其时间复杂度T（n）.
但是在现实程序设计过程中，往往遇到的问题都是比较复杂的算法，就不能很容易地写出规模n的表达式，也比较难总结其时间复杂度. 递归函数就是属于这种情况. 下面举例说明递归函数的时间复杂度的分析方法.

㈤ 二叉树排序的算法时间复杂度问题。依据算法导论，新建二叉树的最佳时间复杂度是nlogn，为啥我推的不是

根据Stirling公式：

将分子取对数，并去掉那些常量和低次项不就是得到O(nlog2n)

㈥ 算法导论里面的大师解法是什么 用大师解法计算下面递归表达式的时间复杂度. T(n)=2T(n/2) + Θ(n^0.1)

#a i从0循环到n，算法复杂度为O(n)。
#b 一共要做n^2/2次加法，算法复杂度为O(n^2)。
#c 要求一个k，满足2^k>=n ，算法复杂度为O(log(n))
#d 注意到这个函数做的事跟#c的函数恰好相反，算法复杂度相同，也是O(log(n))
#e 因为已算出#g每次做3(n-3)次加法，那么i从1到n，一共做2/3*(n^2-5n+6)次加法，所以复杂度为O(n^2)。
#f 这个函数可以写成公式T(n)=T(n-2)+T(n-1)，这个递归式跟黄金分割有关系，解这个递归式，可以知道 T(n) = O((√5-1/2)^n)
#g 函数调用一共做3(n-3)次加法，所以复杂度为O(n)
PenitentSin 这位兄台的#c 算的不对啦，#g也不对。还有#f，这个虽然是递归，但不是递归就等于指数级的复杂度，要解递归方程才能断定的。
关于算法复杂度，《算法导论》一书中第四章有一个主定理，记住这个定理之后，这些问题就小case了（除了复杂递归之外）。

㈦ 请问算法的时间复杂度是怎么计算出来的

首先假设任意一个简单运算的时间都是1，例如a=1;a++;a=a*b;这些运算的时间都是1.

那么例如
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
a++; //注意，这里计算一次的时间是1.
}
那么上面的这个例子的时间复杂度就是 m*n

再例如冒泡排序的时间复杂度是N*N；快排的时间复杂度是log(n)。

详细的情况，建议你看《算法导论》，里面有一章节，具体讲这个的。