O(logn)与算法的关系

Question

我对O(logn) 算法的分析还不太好

因此，如果存在嵌套的 for 循环，其中其内部循环 increases/decreases 乘以或除以其中之一，则它是 Big-theta(logn)，其底数是除以或乘以多少通过？

例如：

for(int i=0;i<n;i++) {
for(int j=1; j<n; j*=5) ...

this is Big-theta(logn) with base 5 since it is multiplied by 5?

另一个例子：

for(int i=n;i>0;i--) {
for(int j=i; j>0; j/=10) ...

this is 
Big-theta(logn) with base 10 since it is divided by 10?

我的意思是，我理解正确了吗？

另一个问题：

Big-theta(logn) 仅适用于嵌套循环？（for循环内的for循环）

Answer 1

如果我们可以计算出特定的 for 循环执行了多少次，那么我们就可以很容易地了解其复杂性。我们可以从一个简单的 for 循环示例开始。

考虑以下for循环，

for(int i=1;i<=m;i++)
{
    //....
}

现在，如果我们想知道这个 for 循环运行了多少次，那么我们可以通过写级数（因为它是均匀级数）来实现，并找出哪个项是 > m(limit).这样我们就可以轻松找到 for 循环所需的迭代次数。

在这个例子中，如果我们写出 i 的所有可能值，

1,2,3,4,5,......,m

这个系列是Arithmetic Progression。现在我们有一个方程式，用于找到序列的 n-th 项为 {a(n) = a(1)+(n-1)*d}。这里 d=1, a(1)=1 现在我们需要找到最大值 n 使得 a(n)<=m.

我们可以通过简单地放置 a(n)=m 并找到值 n 来完成。所以这里

m = 1+ (n-1)*1
m = 1+n-1
m = n
n = m.

所以这里的总迭代次数为 m 因此我们可以说这个 for 循环的复杂度为 O(m).

现在考虑你给出的例子，

for(int j=1; j<n; j*=5)...

在这里，如果你写下 j 的所有值，那么系列将是 1,5,25,125,.....，现在这个系列是 Geometric Progression。查找 n-th 项的公式是 a(n) = a(1)*(r^(n-1))，这里是 a(1)=1 and r=5.

现在用 n(limit) 代替 a(n) 以查看循环执行了多少次，让我们将限制 n 重命名为 m 以消除混淆，

a(n) = a(1)*(r^(n-1))
m = 1*(5^(n-1))
m = 5^(n-1)
Now take log of base 5 on both side
log (m) = (n-1) //log is of base 5
n = log(m)+1

这样我们可以在这里发现所需的总迭代次数为 n = log(m)+1，其中 log 以 5 为底。删除常量后，我们可以说此循环的复杂度为 O(log m)，以 5 为底。

你问题的第二个例子也是这样，如果你写j的系列，你会得到n,n/10,n/100,....所以它也是Geometric Progression和a(1)=n , r= 1/10这里 a(n) 将是 1 因为我们需要找到 term.If 你会找到总迭代次数，你将得到它作为 log n 以 10 为底。

Big-theta(logn) only work for nested loop only? (for loop inside the for loop)

没有必要。假设我们只有一个循环，其格式如下，

for(int i=1;i<=n;i*=2)

这个循环也有 O(log n) 的复杂度，它不是内循环。所以这取决于你的for循环的增量操作。它定义了 for 循环的整体复杂度。

O(logn)与算法的关系

O(logn) and algorithm relationship

algorithm

complexity-theory

discrete-mathematics

big-theta