这段代码可以从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

顺便说一下，这个问题的答案是NO.

只打印结果，没有其他是O(N^2)。在少于O(N^2)的情况下绝对没有办法输出N * (N + 1)字符。

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

#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)。