分析这个函数的时间复杂度

Question

假设do_something是O（1），我该如何计算这个函数的时间复杂度？

function run(n) { 
    for(var i = 1; i <= n; i++) { 
    var counter = 1; 
    while(counter <= n) { 
     for (var j = counter; j >= 1; j--) { 
      do_something(); 
     } 
     counter = counter * 2; 
    } 

    } 
} 

我假设循环的初始意味着复杂度将是n，内部while循环意味着log（n）。这是真的？

如何计算一切的复杂性？ 谢谢。

Answer 1

计算一切复杂性并不是微不足道的，因为存在没有确切分析已知的函数（例如collat​​z猜想）。在这种情况下，你可以做一个经验分析，你猜猜哪个运行时间等级最匹配。

关系到你的样品：

1. for循环外被称为n次
2. while循环被称为的log（n）次
3. 内的循环，其中计数器的增长被称为柜台倍2^M。但计数器是重新计算的log（n）次

这意味着循环（2^m）的内部指数被称为m = log（n）次。 所以你有2 ^（log n）= n log（2）= n

你也可以做反之亦然。内部指数函数称为日志时间。表示log（2^m） - >（2^n = 2^m） - > m = n。

您还可以简单地创建从m = 0到m = log（n）的2^m之和，即2n-1 - > O（n）。

然后，您必须将outer for loop的线性时间乘以while循环的线性时间（包括inner for loop）。所以你有O（n * n）= O（n²）时间。

Answer 2

可以计算确切的步骤数量。

1. 外部循环运行Ñ倍
2. 的同时和最内循环运行计数器次，每次计数器的值，这些是1, 2, 4, 8, ..., 2^(bitLength(n)-1) ，其总结于2^bitLength(n) - 1

其中bitLength(n) = trunc(ln(n)/ln(2))+1

这两个数据相乘，得出台阶的确切金额：

n * (2^bitLength(n) - 1)

近似的复杂性是为O（n ），因为O(2^bitLength(n) - 1) = O(n)