2 sinat 32951601 sinat_32951601 于 2016.09.26 21:39 提问

求助。分析时间复杂度与问题规模间的关系。

int fun_b(int N)
{
if (N<=1) return 100;
else return fun_b(N/2) * fun_b(N/2 - 1);
}

2个回答

qq_29594393
qq_29594393   Ds   Rxr 2016.09.26 21:51
已采纳

小于等于1 return 100 其他的return 10000,时间复杂度应该是
log 2 di N^2

caozhy
caozhy 正解
接近 2 年之前 回复
wzxq123
wzxq123   Rxr 2016.09.26 22:04

两个都是log2N(2是底数)所以最后是log2N(2是底数)的平方。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
常见的时间复杂度所对应的数据规模
嗯 通常一秒内10^6肯定能过 10^7有点勉强 10^8。。就悬了O(logn) 额 非常大 long long内都可以O(n) 10^7O(nlogn) 10^5 ~ 5 * 10^5O(n^2) 1000 ~ 5000O(n^3) 200 ~ 500O(2^n) 20 ~ 24O(n!) 12
时间复杂度的解析
时间复杂度1.时间复杂度的定义一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 ),简称时间复杂度。 定义:如果一个问题的规模是n,解这一问题的某一
算法的复杂度——算法的时间复杂度和空间复杂度
在一次笔试题目中,发现了自己对于算法的时间复杂度问题上并没有完全清晰这个概念和计算方法,故上网寻找到比较好的详细介绍来学习。 算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少
【算法复杂度分析】主定理
规模为n的问题通过分治,得到a个规模为n/b的问题,每次递归带来的额外计算为c(n^d) T(n) <= aT(n/b)+c(n^d) 那么就可以得到问题的复杂度为: T(n) = O(n^d log(n)), if a = b^d T(n) = O(n^d ), if a < b^d T(n) = O(n^logb(a))), if a > b^d 可见,
玩转算法面试-数据规模,时间复杂度,均摊复杂度(笔记)
数据规模时间复杂度 并不是所有的双层循环都是O(n^2)的 复杂度实验来确定复杂度 // O(N) 两倍增加 int findMax( int arr[], int n ){ assert( n &gt; 0 ); int res = arr[0]; for( int i = 1 ; i &lt; n ; i ++ ) if( ar
矩阵乘法时间复杂度Matlab演示
使用Matlab内置函数统计矩阵乘法所耗时间,给出时间复杂度图示,定量理解复杂度与问题规模的关系。
常见问题时间复杂度的计算过程
时间复杂度的计算过程是由特殊到一般的过程,使用特殊的数值得到普遍的规律,而结果却是一个概数,但这种结果已经足够让我们作为依据评论一个算法的优劣。 同时也让我们明白,算法的执行次数尽管复杂多变,我们只要取平均或最差情况,就能实现自己的目的。
分治法与动态规划
1. 分治法与动态规划主要共同点: 二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解.   2. 分治法与动态规划实现方法: ① 分治法通常利用递归求解. ② 动态规划通常利用迭代法自底向上求解,但也能用具有记忆功能的递归法自顶向下求解.   3. 分治法与动态规划主要
作业3 算法时间复杂度和空间复杂度
1-1 2​N​​和N​N​​具有相同的增长速度。 (2分) T         F 1-2 N​2​​logN和NlogN​2​​具有相同的增长速度。 (2分) T         F 1-3 在任何情况下,时间复杂度为O(n​2​​) 的算法比时间复杂度为O(n*logn)的算法所花费的时间都长。 (1分) T  
时间复杂度一定的算法1s内能处理的问题规模上限
复杂度 数量级 最大规模 O(logN) >>10^20 很大 O(N^1/2) 10^12 10^14 O(N) 10^6 10^7 O(NlogN) 10^5 10^6 O(N^2) 1000 2500 O(N^3) 100 500 O(N^4) 50 50 O(2^N) 20 20 O(3^N) 14 15 O(N!) 9 10