程序的時間複雜度？

Question

1 i ← 1 
2 while i < n/4 
3 do 
4 j ← 2i 
5  while j < n 
6  do 
7   j ← j + 1 
8  i ← i + 1 


b) 1 i ← n 
    2 while i > 1 
    3 do 
    4 j ← i 
    5 while j < n 
    6  do 
    7  j ← 2j 
    8 i ← i − 1 


c) 1 i ← 1 
    2 while i < n 
    3 do 
    4  j ← 0 
    5  while j ≤ i 
    6  do 
    7   j ← j + 1 
    8  i ← 2i 

鑑於這三個程序，找出每一個程序的時間複雜度最簡單的方法是什麼？我可以說第一個可能是O（n^2）。但是有沒有簡單的方法來解決這些問題？我明天就考試了。

Answer 1

（我會忽略掉乘1，四捨五入等在求和限制）

---

A）

在內環你n - 2i - 1操作。在外部循環中，您可以執行n/4 - 1。因此，複雜性是：

所以你的答案，第一個是正確的。

---

B）

在內環，j得到每次加倍，所以呈指數增長;因此內部循環需要對數時間 - log (n/i)。 （基數2但忽略WLOG）。 i裏面的除法是因爲j從i開始，所以相當於從1開始，長到n/i。在外層循環中，您可以使用n - 1 ops。

（最後一步是從斯特林的近似值）

---

C）

在內環你做i + 1歡聲笑語。在外環i從1到n成指數增長，所以log n。

---

注：我注意到TypeKazt的答案存在顯着差異;這說明您不能簡單地將內環的複雜性與外環的複雜性「相乘」，並且內環的邊界條件具有確定性的重要性。

---

編輯：由於添加證明我對TypeKazt大膽指責（嘿嘿對不起，哥們），這裏是一些測試數據，我從一個C＃實現了：

由於您可以看到，A（線性標度）的複雜度爲O(n^2)，而B和C（對數標度標度）的線性爲線性。

代碼：

static int A(int n) 
{ 
    int c = 0; 
    for (int i = 0; i < n/4; i++) 
     for (int j = 2 * i; j < n; j++) 
     c++; 
    return c; 
} 

static int B(int n) 
{ 
    int c = 0; 
    for (int i = n; i > 1; i--) 
     for (int j = i; j < n; j *= 2) 
     c++; 
    return c; 
} 

static int C(int n) 
{ 
    int c = 0; 
    for (int i = 1; i < n; i *= 2) 
     for (int j = 0; j <= i; j++) 
     c++; 
    return c; 
} 

---

附：我知道SO的政策不是照顧人，但我通過實例學習得很好，所以我希望這能幫助你理解一個簡單的分析複雜性分析方法。