函数的Big-O示例
函数的Big-O示例
提问于 2018-10-05 01:01:39
我有这个函数：
function void myFoo(int num, int count) {
if (num == 0) return;
for (int x = 0; x < count; x++) {
for (int y = x; y < count; y++) {
for (int z = y; z < count; z++) {
//O(1) computation
}
}
num--;
myFoo(num, count);
}
}我只是想知道这个函数的复杂性，它是Big-o (n!)吗？
回答 1
Stack Overflow用户
发布于 2018-10-09 23:54:31
我将假设num和count都是非负的。运行时间T(m，n)，其中m，n是对数和对数的大小(即num (num)，count (count))，由下式给出
T(m, n)=sum(T(log(2^m-1), n)+sum(sum(O(1), z=y..2^n-1), y=x..2^n-1), x=0..2^n-1)这可以简化为
T(m, n)=2^n*T(log(2^m-1), n)+2^n/3+2^(2n-1)+2^(3n-1)/3给予
T(m, n)=2^n*T(log(2^m-1), n)+O(2^(3n))观察到这并不依赖于m，除了它被递归应用2^m次之外，我们得到
T(m, n)=sum(2^(k*n)*O(2^(3n)), k=0..2^m-1)，它与
T(m, n)=O((8^n*(-1 + 2^(2^m*n)))/(-1 + 2^n))=O(2^((2^m+2)n))=O(2^(2n)*2^(2^m*n))因此，将输入度量为每个数字的大小(并推广到允许任意大小的整数)，其复杂性比m中的双指数更差。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52652017
复制相关文章
相似问题
腾讯云开发者
