找到"有循环,有方法调用"的大哦

Question

我试图找到这个代码的大哦,

for(int i=0;i<n;i*=2)
fun(n);

其中fun()是一个复杂度为o(n ^ 2)的方法

我认为该for 陈述具有o(log n)的复杂性.所以,所有代码的大哦都是o(n ^ 2logn).我对吗？

Answer 1

它是O(无限),因为你将i初始化为0然后将每次迭代乘以2.

@Eugene如果`n`为0或负数,它甚至不会启动循环,但如果`n`是正整数,_BarrySW19_确实是正确的.`i`被初始化为0,并且每次迭代都保持为0,因为`0*2 = 0`,所以`i <n`将始终保持真实. (2认同)