代码以下代码的时间复杂性?[英] Time complexity of the code below?

本文是小编为大家收集整理的关于代码以下代码的时间复杂性?的处理方法,想解了代码以下代码的时间复杂性?的问题怎么解决?代码以下代码的时间复杂性?问题的解决办法?代码以下代码的时间复杂性?问题的解决方案?那么可以参考本文帮助大家快速定位并解决问题,译文如有不准确的地方,大家可以切到English参考源文内容。

问题描述

有人可以告诉我以下代码的时间复杂性吗?

#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

因此,输入一次反向遍历,然后再向前遍历一次,但是在步骤2中不回到先前读取的位置.然后从步骤3切换时.它直接调整了迭代器. 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(1)) O(n)算法仍然是O(n)(忽略常数).

其他推荐答案

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

您的代码中只有一个用于循环,其索引I线性变化. 这就是为什么它的O(n)

本文地址:https://www.itbaoku.cn/post/67913.html

问题描述

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

其他推荐答案

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

There is only one for loop in your code and its index i is varying linearly . Thats why its O(n)

查看更多