下面代碼的時間複雜度？

Question

有人能告訴我以下代碼的時間複雜度嗎？

#include<iostream> 
#include<string.h> 
using namespace std; 
int main() 
{ 
char a[100]= "Gosh I am confused :D"; 
int i,count= -1,display_ToVal= strlen(a)-1, display_FromVal; 

for(i=strlen(a)-1 ; i>=0 ; i=i+count) 
{ 
     if ((a[i] == ' ' || i == 0) && count == -1) 
     { 
     cout << " "; 
     display_FromVal = i; 
     count = 1; 
     if (i == 0) 
       cout << a[i]; 
     continue; 
     }  

     else if(count == 1 && i == display_ToVal) 
     { 
     cout << a[i]; 
     display_ToVal = display_FromVal - 1; 
     i = display_FromVal; 
     count = -1; 
     if(display_FromVal == 0) 
       break; 
     else 
       continue; 
     } 

     else if (count == 1) 
     cout << a[i]; 

     else 
     continue; 
} 

return 1; 
} 

我是否這可以被歸類爲O（n）的真的很困惑。請提前幫助，謝謝。

Answer 1

該算法可在僞代碼summarrized爲：

1. 標記當前位置
2. 直到空間被發現或結束在時間上向後移動一個字符去輸入達到
3. 現在前進複製每個字符輸出，然後回到1，除非達到

EOI所以輸入被逆向工程＆走過一次se，再前進一次，但在步驟2或3中沒有返回到先前讀取的位置。並且當從步驟3切換到1時，它直接調整迭代器。變量count用於跟蹤算法的狀態（它實際上是一個簡單的狀態機）。它也被重用來定義迭代的方向。

所以，該算法實際上是O(n)。

---

爲了更清楚，它可以被改寫，因爲這，在不改變的複雜性：

void printStringWithWordReversed(const char* a) { 
    int i,j,display_ToVal= strlen(a)-1, display_FromVal; 
    for(i=display_ToVal; i>=0 ; i=i+-1) 
    { 
     if ((a[i] == ' ' || i == 0)) 
     { 
     // When entering this branch, we are switching from state 2 to 
     // state 3 (this is the content of the first branch). 
     cout << " "; 
     display_FromVal = i; 
     if (i == 0) 
       cout << a[i]; 
     // This loop correspond to the state 3, and is equivalent to the 
     // previous code in the particular case when count == 1. 
     for (j = display_FromVal+1; j <= display_ToVal; j=j+1) 
     { 
      cout << a[j]; 
     } 
     // This postlude correspond to the transition from state 3 to state 1 
     // and correspond to the second branch in the original algorithm. 
     display_ToVal = display_FromVal - 1; 
     if (i == 0) 
      break; 
     continue; 
     }  
    } 
} 

所以我們查找每個字從最終輸出他們以正確的順序啓動。這顯然是O(n)既實現（在時間和空間，如果我們假設cout爲char插入運營商O(1)），因爲O(n)算法的加入固定數量（此處爲兩個）還是O(n)（常數被忽略）。

Answer 2

「{對於（I = strlen的（A）-1; I> = 0; I = I +計數）}」

只有一個代碼中的循環和它的索引i被線性變化。 所以它爲O（n）