时间戳

首页 > 解决方案 > 这个算法的复杂度是多少？

algorithm - 这个算法的复杂度是多少？

问题描述

你可以解决这个问题：这个算法的复杂度是多少？

for(int i=0;i<n;i++)
   i*=m;

标签： algorithmruntimecomplexity-theory

解决方案

考虑i每一步的顺序：

 0    =>  0
 1    =>  m
 m+1  =>  m^2+m   
 m^2+m+1 => m^3+m^2+m
 m^3+m^2+m+1 => m^4+m^3+m^2+m

所以我们可以看到 的多项式m，并且已知

m^k+m^(k-1)+...+1 = m^(k+1)/(m-1)    //might be checked with multiplication by (m-1)

这个表达式应该达到n，所以粗略估计是

 m^k~n
 k = log(n) base m   //number of steps

我们可以忽略对数底，因此步骤数和操作数（每个循环步骤的操作数是恒定的）估计为O(log(n))

推荐阅读