Сроки выполнения кода ниже?

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., за исключением случаев ВЗ достигается

Так вход проходится один раз в Rever 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; 
     }  
    } 
} 

Таким образом, мы LookUp каждое слово, начиная с конца и вывода их в правильном порядке. Это явно O(n) как с реализацией (во времени и пространстве, если мы предположим, что cout вставки оператор char является O(1)), поскольку добавление фиксированное число (здесь два) O(n) алгоритма еще O(n) (константа игнорируется).

Answer 2

"{для (я = StrLen (а) -1; я> = 0; I = I + счетчик)}"

Существует только один цикл в коде и индекс я варьируется линейно , Вот почему его О (п)