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循環的整體複雜性。