谁可以告诉我的时间复杂度为以下code？

Can someone tell me the time complexity for the following code?

#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）的。请帮忙，谢谢你在前进。

I am really confused as to whether this can be classified as O(n). Please help, thank you in advance.

推荐答案

该算法可以在假code被summarrized为：

The algorithm can be summarrized in pseudo-code as :

所以输入遍历一次在倒车时，和一个更多的时间前进，但是没有回来到previously读取位置在任一步骤2或3。当从第3步，直接切换到1。调整迭代器。该计数变量用于跟踪算法的状态（它实际上是一个简单的状态机）。它也被重新使用来定义迭代的方向

So the input is traversed once in reverse, and one more time forward, but without coming back to a previously read position in either step 2. or 3. And when switching from step 3. to 1. it directly adjust the iterator. The count variable is used to track the state of the algorithm (it is in fact a simple state-machine). It is also reused to define the direction of the iteration.

因此​​，该算法实际上是在 O（N）。

So, the algorithm is in fact O(n).

有关更清楚，它可以重写为此，在不改变的复杂性：

For more clarity, it could be rewritten as this, without changing the complexity:

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 插入运算符字符是 O（1）），因为加入的（这里两者的固定号码） O（N）算法仍然 O（N）（常量被忽略）。

So we lookup each word starting from the end and output them in correct order. This is clearly O(n) with both implementation (both in time and space if we assume that cout insertion operator for char is O(1)) since adding a fixed number (here two) of O(n) algorithm is still O(n) (the constant is ignored).