时间这个算法有两个for循环的复杂性 [英] time complexity for this algorithm with two for loops

问题描述

你能解释我如何找到时间，这种复杂性

Can you explain me how to find time complexity for this

sum1=0;
for(k=1;k<=n;k*=2)
  for(j=1;j<n;j++)
     sum++

氮

我正在考虑为基础，并试图计算多少迭代发生在

I am taking consideration of N as base, and tried calculating how many iteration happens when

n=1,2,3...n

但我不能genralize它。 请有人解释我，彻底。 我甚至查同类型的其它问题，如： 称它遵循

But i am not able to genralize it. PLease some one explain me, thoroughly. I have even checked other queries of similar type like: saying it follows

1,2,4,8...n so it will be
2^n
nlogn

但我力明白。 我不知道他们是怎么说的 2的n次方= LOGN 。 请任何适当的解释如何计算一步步..

But i dint understand. I dont know how they say 2^n=logn. Please any properly explain how to calculate step by step..

感谢：）

推荐答案

K 呈指数增长，因此需要 O（log n）的时间达到 N 。检查对数的定义。这是你的外环。

k grows exponentially, so it takes O(log n) time to reach n. Check the definition of logarithm. That's your outer loop.

内环是一个简单的 O（N）。

这篇关于时间这个算法有两个for循环的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！