时间循环的复杂性由两个或三个乘以值 [英] Time complexity of loop multiplying the value by two or three

问题描述

我发现下面的for循环中的SO问题。

我发现，时间复杂度为为O（n log n）的。

我

如何找到时间的复杂性，如果我们改变 K * = 2 到 K * = 3 ？

  //'诠释N'某处定义
INT变种= 0;
对于（INT K = 1; K＆LT; = N，K * = 2）
   对于（INT J = 1; J＆LT; = N; J ++）
      VAR ++;
 

解决方案

的时间复杂度仍然是为O（n log n）的。

有关 K * = 2 的登录将基地2个。

有关 K * = 3 的登录将基地3。

但变化日志的基础只影响的结果常数因子（这可以从事实推导出登录<子> b 在 = 登录<子> C A /日志<子> C B ，为任何基 C ），这是在大O表示法忽略，因此它们具有相同的时间复杂度。

---

我们在哪里得到日志 2 N 的呢？

嗯， K 的值是这样的：

  1，2，4，8，16，...，2  M 对于某些m，其中2  M ＆LT ; = N＆LT; 2  M + 1 
= 2  0  + 2  1  + 2  2  + ... + 2  M 
 

当然，也有刚 M + 1 （ 0 到 M ）项以上，使循环运行 M + 1 倍。

现在，如果我们可以用一些基本的对数，以获取 M 而言 N ：

  2  M  = CN对于某一常数c，其中1＆LT; = C＆LT; 2
日志 2  2  M  =登录 2 （CN）
M登入， 2  2 =日志 2 （c.n）
M.1 =日志 2  C +登录 2 ñ
M = O（日志 2  C +登录 2  N）
  = O（日志 2  N）//常数项可以忽略不计
 

我们也可以遵循 K完全相同的方法，因为上面的* = 3 ，只需更换 2 按 3 。

I found the below for-loop in an SO question.

I found that the time complexity is O(n log n).

How would I find the time complexity if we change k *= 2 to k *= 3?

// 'int n' is defined somewhere
int var = 0;
for (int k = 1; k <= n; k *= 2)
   for (int j = 1; j <= n; j++)
      var++;

解决方案

The time complexity would still be O(n log n).

For k *= 2, the log would be base 2.

For k *= 3, the log would be base 3.

But change in the base of log only affects the result by a constant factor (this can be derived from the fact that logba = logca / logcb, for any base c), which is ignored in big-O notation, thus they have the same time complexity.

---

Where do we get log2n from anyway?

Well, the values of k goes like this:

1, 2, 4, 8, 16, ..., 2m  for some m, where 2m <= n < 2m+1
= 20 + 21 + 22 + ... + 2m

And of course there are just m+1 (0 to m) terms above, so the loop runs m+1 times.

Now if we can use some basic logarithms to get m in terms of n:

2m = c.n   for some constant c, where 1 <= c < 2
log22m = log2(c.n)
m log22 = log2(c.n)
m.1 = log2c + log2n
m = O(log2c + log2n)
  = O(log2n)               // constant terms can be ignored

We can also follow the exact same approach as above for k *= 3 by just replacing 2 by 3.

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