Mik*_*ike 2 java complexity-theory runtime
for(int i=1; i<n; i=2*i)
// simple addition performed here...
我理解O(n)运行时单循环和O(n ^ 2)嵌套循环但是这个循环的运行时也是n log n,因为乘法？
谢谢,
不,你是正确的,这里有乘法,但它有助于减少增加的运行时间,而不是增加它.
您必须根据输入值查看循环的完成速度n.因为n = 128,你会得到i = 1, 2, 4, 8, 16, 32, 64, 128.如果你加倍n,那就不会像O(n)那样加倍,并且它肯定不会像O(n 2)那样乘以4 .它只是在循环中再添加一次迭代.
这就是所谓的O(log N)时间复杂度.运行时间随着输入值的对数而上升,并且通常在平衡二叉树搜索中看到,其中您可以在每次迭代时移除剩余搜索空间的一半.
| 归档时间： |
|
| 查看次数： |
5880 次 |
| 最近记录： |