O（logn）时间和算法关系

Question

我不能仍然得到很好有关分析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? 

我是说，我得到它正确？

另一个问题：

大-θ（LOGN）仅只有嵌套循环工作？ （for循环内的循环）

Answer 1

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

试想，如果我们想找到这个for环路，则多少时间运行，我们可以通过编写一系列做到这一点（因为它是一系列均匀），并找到环以下，

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

现在这里那个术语是> m(limit)。通过这种方式，我们可以轻松找到for循环所需的迭代次数。

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

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)。如果你写的j然后系列的所有值将1,5,25,125,.....，现在这个系列是Geometric Progression

现在考虑您给了一个例子，

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

这里。找到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

大-theta（logn）仅适用于嵌套循环吗？ （For循环内的循环）

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

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

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