algorithm - 具有两个 for 循环的该算法的时间复杂度

Question

你能解释一下如何计算时间复杂度吗

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

我正在考虑以 N 为基数，并尝试计算当

n=1,2,3...n

但我无法概括它。 请有人彻底解释我。 我什至检查了其他类似类型的查询，例如: 说它跟随

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

但我不明白。 我不知道他们怎么说 2^n=logn。 请任何正确解释如何逐步计算..

谢谢:)

Answer 1

k 呈指数增长，因此需要 O(log n) 时间才能达到 n。检查 logarithm 的定义.那是你的外循环。

内部循环是一个简单的O(n)。