打印X形图案的C++代码能否从O(n²)优化至O(n)时间复杂度？

待优化原始代码 #

#include <iostream>
using namespace std;
int main() {
  // 打印X形的尺寸，建议使用奇数
  int size = 5;
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) { 
      if (i == j || i + j == size - 1) {
        cout << "*";
      } else {
        cout << " ";
      }
    }
    cout << "\n";
  }
  return 0;
}

原始代码运行输出 #

*   *
 * *
  *
 * *
*   *

复杂度优化结论 #

不存在严格符合算法复杂度定义的O(n)时间复杂度实现，原因如下：

• n阶X形图案总共有n行，每行包含n个字符（含空格、星号），完整输出整个图案的总字符数是n²量级。所有需要逐字符生成、输出完整图案的逻辑，操作次数的理论下界是Ω(n²)，不可能突破这个量级做到O(n)。
• 网上流传的所谓"O(n)优化"本质都是降低常数开销的写法，没有改变复杂度量级：
  • 一类写法是预先构造每行的字符串，把内层逐位置判断的逻辑替换为直接修改两个星号位置、其余位置默认填充空格，比原始双层循环写法减少了条件判断次数，但构造长度为n的行字符串、输出整行的操作总次数依然和n²成正比，复杂度还是O(n²)。参考优化写法如下：

    #include <iostream>
    #include <string>
    using namespace std;
    int main() {
      int size = 5;
      for (int i = 0; i < size; i++) {
        string line(size, ' ');
        line[i] = '*';
        line[size - 1 - i] = '*';
        cout << line << '\n';
      }
      return 0;
    }
    

  • 另一类写法是跳过空格输出，通过控制终端光标位置直接在两个星号的对应位置打印字符，看似省略了空格输出步骤，但终端光标移动的操作开销和逐字符打印没有本质差异，总耗时依然随n²增长，不属于O(n)实现。

内容的提问来源于stack exchange，提问作者Anurag Dutta