以下のコードの時間の複雑さは？

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. 現在の位置をマークスペースが見つかった、または終了されるまで、一度に1つの文字を行きます入力は今EOIだから入力がreverに一度横断する

達した場合を除いて、1に戻って、その後、出力に各文字をコピーする前に進む

に達しています1つ前の位置に戻ることはありません。また、手順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)アルゴリズムの固定数を（ここでは2つ）追加するので、明らかO(n)両方の実装と（両方の時間と空間で、我々はcharためcout挿入オペレータがO(1)であると仮定した場合）である（定数は無視されます）まだO(n)です。

Answer 2

"{（I =のSTRLEN（A）-1; I> = 0; iが= iがカウント+）ため}"

つのみコードとそのインデックスにおけるループのiが直線的に変化しているがあり。そのO（N）