大哦符号循环操作

Question

如果我有两个嵌套循环，其中外部有一个很大的哦符号 logn 并且内部有 n 之一，这是否意味着整体概念将是 log2n？因为每次外循环执行时 n 都会改变，所以内循环在技术上是运行 logn 次，但它循环了 n 次。如果这个问题听起来很愚蠢，我深表歉意。这是循环的样子：

outer loop runs while n>0
   inner loops runs n times
   n=(1/4)n

很抱歉，如果我的格式不正确，我花了几分钟试图弄清楚如何在这里使用乳胶，但无法完全破解它

Answer 1

时间复杂度为O(n):

First time, inner loop iterates n times
Second time, inner loop iterates n/4 times
Third time, inner loop iterates n/16 times
...
K'th time, inner loop iterates n/(4^k) times

总结一下：

n + n/4 + n/16 + ... + n/4^k + ... + n/(4^log_4(n))

这是 sum of geometric series 和：

a = n
r = 1/4

根据 r < 1

的公式，它的总和受限于：(n/3/4) = 4n/3

大哦符号循环操作

Big Oh notation loop manipulation

big-o

nested-loops