这段代码可以从 O(n^2) 进一步优化到 O(n) 吗？

Question

这是需要优化的代码

#include <iostream>
    using namespace std;
    int main() {
      // size of cross, use odd number
      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;
    }

输出

*   *
 * *
  *
 * *
*   *

请让我知道任何来源或参考文献（如果有）...

Answer 1

顺便说一句，这个问题的答案是否定的。

只是打印结果，没有别的O(N^2)。绝对没有办法输出N * (N + 1)小于的字符O(N^2)。

您可以通过在编译时计算所有内容来提高代码的性能：

#include <cstdio>
#include <array>

template <int size>
constexpr auto cross() {
    std::array<char, size * (size + 1) + 1> arr;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) { 
            if (i==j || i+j==size-1) {
                arr[i * (size + 1) + j] = '*';
            } else {
                arr[i * (size + 1) + j] = ' ';
            }
        }
        arr[i * (size + 1) + size] = '\n';
    }
    arr[arr.size() - 1] = 0;
    return arr;
}

int main() {
    // size of cross, use odd number
    const auto t = cross<5>();
    puts(t.data());
    return 0;
}

https://godbolt.org/z/WdWdTYcvK

这优化至puts("* *\n * * \n * \n * * \n* *\n");，即O(N^2)。