Временная сложность кода ниже?

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

Алгоритм можно суммировать в псевдокоде как:

1. отметка текущей позиции
2. переходите назад на один символ за раз, пока не будет найден пробел или достигнут конец ввода
3. теперь идите вперед, копируя каждый символ для вывода, затем вернитесь к 1., за исключением случаев, когда достигнут eoi

Таким образом, входной сигнал перемещается один раз в обратном направлении и еще один раз вперед, но без возврата к ранее прочитанному положению на шаге 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

"{for (i = strlen (a) -1; i> = 0; i = i + count)}"

В вашем коде только один цикл for, и его индекс i меняетсялинейноВот почему его O (N)