时间复杂度的代码如下？ [英] Time complexity of the code below?

问题描述

有人能告诉我以下代码的时间复杂度吗？

 ＃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）。请帮助，先谢谢。

解决方案

该算法可以用伪代码概括为：

1. 标记当前位置


2. 一次后退一个字符，直到找到空格或输入结束


3. 现在前进将每个字符复制到输出，然后返回到1.，除非达到eoi。

$ b b

因此，输入被反向遍历一次，再往前一遍，但不会回到步骤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））
 {
 //当进入这个分支时，我们从状态2切换到
 //状态3（这是第一个分支的内容）。 
 cout<< ; 
 display_FromVal = i; 
 if（i == 0）
 cout<< a [i]; 
 //这个循环对应于状态3，并且等于
 //在count == 1的特定情况下的前面的代码。
 for（j = display_FromVal + 1; j < = display_ToVal; j = j + 1）
 {
 cout< a [j]; 
} 
 //这个postlude对应于从状态3到状态1的转换
 //并且对应于原始算法中的第二分支。 
 display_ToVal = display_FromVal  -  1; 
 if（i == 0）
 break; 
 continue; 
} 
} 
} 
  

从最后并以正确的顺序输出它们。这显然是 O（n）两个实现（在时间和空间，如果我们假设 cout 插入运算符 char 是 O（1）），因为添加了一个 O（n）算法仍然是 O（n） $ b

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;
} 

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

解决方案

The algorithm can be summarrized in pseudo-code as :

1. mark the current position
2. go backward one character at a time until a space is found or end of input is reached
3. now go forward copying each character to output, then go back to 1., except if eoi is reached

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.

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;
        }       
    }
}

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).

这篇关于时间复杂度的代码如下？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！