这个算法的时间复杂度是多少（uVa Online Judge 483 - Word Scramble）？

Question

我正在努力提高我对时间复杂度分析的理解。这是我解决的问题：

uVa在线评委 483 - 单词争夺

编写一个程序，在保留单词本身顺序的同时，反转单词序列中每个单词的字母。输入文件将由几行几个单词组成。单词是由白色 space 分隔的连续可打印字符。输出将包含与输入文件相同的行和词。但是，每个单词中的字母必须颠倒。

示例输入

我爱你。你爱我。我们是幸福的一家人。

示例输出

我进化.uoy uoY evol .em 呃 yppah .ylimaf

这是我的代码：

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;


int main(int argc, char *argv[]) {

 char  ch;
 stack<char> word;

  while (cin.get(ch)) {
    if (!isspace(ch)) {
      word.push(ch);
    } else {
      while (!word.empty()) {
        cout << word.top(); 
        word.pop();
      }
      cout << ch;
    }
  }

  return 0;
}

我认为是大O(n)，其中n是字符总数。出于某种原因，当有嵌套循环时我会感到困惑。我的思路是查看输入大小，并计算对其进行的每个操作。所有操作的最坏情况是 O(n)（堆栈的压入操作）。听起来对吗？

谢谢

Answer 1

有两种情况——字符是 space 或者不是。如果字符是 space，它会被直接打印出来（这样一个操作）。否则，该字符被添加到堆栈中，随后恰好从该堆栈中弹出一次（当遇到 space 字符时）。因此，您最多对每个字符执行两个操作 - 压入和弹出。总体而言，您最多执行 2 * n 个操作，这意味着 O(n).

Answer 2

是的，如果字符总数为n，则为O(n)。复杂性主要受 for 和 while 等循环的影响，因为这是您的多次迭代所在。

您还可以用另一种方式解释时间复杂度。它可以称为 O(m*n)，其中 n 是单词数，m 是每个单词中的字符数。

这个算法的时间复杂度是多少（uVa Online Judge 483 - Word Scramble）？

What is the time complexity of this algorithm (uVa Online Judge 483 - Word Scrammble)?

c++

algorithm

time-complexity