代码之家 › 专栏 › 技术社区 › cstac

复杂度算法递推关系

master-theorem recurrence complexity-theory math algorithm

cstac · 技术社区 · 10 年前

int function(int n){
if (n<=1)
 return 1;
else 
 return (2*function(n/2));
}

运行时间的递推关系T(n)是什么?为什么?

2 回复 | 直到 10 年前

user4668606 user4668606 10 年前

该算法的复杂度函数为

T(n) = T(n / 2) + 1
T(1) = 1

应用 master-theorem ,我们会得到

a = 1
b = 2
c = 0 (1 = n^0)

log b(A) = log2(1) = 0 = 0 c, thus case 2
apply values and the result is O(log n).

正如@guillaume已经正确指出的那样,使用线性函数可以更容易地解决这个问题。

guillaume girod-vitouchkina 10 年前

你可以直接计算:它是最接近的2^n,最大或相等。

计算L=log2(n),取2^L或2^(L+1)

复杂性为O(log2N):log2N操作。

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

1 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

1 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

1 年前