O(logn)与算法关系

Question

我仍然不能很好地分析O(logn)算法

因此，如果有嵌套的for循环，它的内环增加或减少了一个乘积或除法，那么它的基是多少被除以或乘以多少，就是大θ(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?

我是说，我猜对了吗？

另一个问题：

大θ(Logn)只适用于嵌套循环？(for循环在for循环中)

Answer 1

如果我们能够计算一个特定的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，其中日志的基值为5。除去常量后，我们可以说这个循环具有基5的O(log m)的复杂性。

对于第二个问题的例子，如果您编写了j系列，您将得到n,n/10,n/100,....，所以它也是带a(1)=n , r= 1/10的Geometric Progression，在这里，a(n)将是1，因为我们需要找到总迭代的term.If，这样就可以得到基为10的log n。

大θ(Logn)只适用于嵌套循环？(for循环在for循环中)

这是不必要的。假设我们只有一个循环，它的格式如下，

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

这个循环还具有O(log n)复杂性，它不是一个内环。这取决于for循环的增量操作。它定义了for循环的总体复杂性。