我仍然不能很好地分析O(logn)算法
因此，如果存在嵌套的 for 循环，其内部循环通过乘法或除法之一增加/减少，那么它是 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 循环)
如果我们能计算出一个特定的for循环被执行了多少次，那么我们就可以很容易地了解复杂性。我们可以从一个简单的 for 循环示例开始。
考虑以下 for 循环，
for(int i=1;i<=m;i++)
{
//....
}
现在在这里，如果我们想找到这个for循环运行了多少次，那么我们可以通过编写序列(因为它是均匀系列)并找到哪个项是> m(limit).这样，我们可以轻松找到该for循环所需的迭代次数。
在这个例子中，如果我们写下 i 的所有可能值，
1,2,3,4,5,......,m
这个系列是算术级数。现在我们有一个方程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,.....，现在这个系列是几何级数。查找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 为底。删除常量后，我们可以说这个循环的复杂性与底数 5 的O(log m)。
对于您问题的第二个示例也是如此，如果您编写一系列j，您将获得n,n/10,n/100,....，因此它也与a(1)=n , r= 1/10Geometric Progression，在这里a(n)会1，因为我们需要找到该术语。如果您找到总迭代次数，您将获得以 10 为基数的log n。
Big-theta(logn) 仅适用于嵌套循环？(for 循环内 for 循环)
没有必要。假设我们只有一个循环，它具有以下格式，
for(int i=1;i<=n;i*=2)
此循环也具有O(log n)复杂性，它不是内部循环。因此，这取决于 for 循环的增量操作。它定义了 for 循环的整体复杂性。