时间复杂度为 O(n) 的金字塔模式问题？

Question

最近，我在 Facebook 群组中看到有人要求使用单个 while 循环在 N 行中打印 '*' 金字塔图案的解决方案.

我发现 post 中的大部分答案都使用语言的语法糖（如 '*'*N;）或使用内置方法，如 .charAt()，例如，这在技术上在我假设的语法或方法中循环？

当代码中只有1个循环时，我们如何计算时间复杂度？会算成O(N)时间复杂度吗？

如果我们只使用

While 循环
整型变量
标准输入输出
If else 条件

要打印图案（如果可能的话？）

标准输出（如 printf()）总是需要 N x N 时间来打印包括 '*' star symbol and ' ' space character in each line which would be theta(N^2) time complexity 如果我理解正确的话？

或者是否有其他方法仅使用 O(N) 或 theta(N) 来打印图案？

或者我完全错过了关于循环和时间复杂度的概念？

Answer 1

如果 n 是金字塔的高度或宽度，则 briks/*s 的数量将为 O(n^2)。三角形的面积是 (height*width) / 2（因此 O(n^2)，其中 n 是高度或宽度），花哨的编程无法改变它。

但是，如果未定义 n，那么您可以将其定义为字符数——然后您可以使用单个循环执行以下操作

/**
 * builds an asterisk pyramid with a single loop
 * n = number of characters in the pyramid, including spaces & line-breaks
 * (use n = 2*o*o, such as 32 (o=4 layers), if you want pretty pyramids)
 */
function pyramid(n) {
   let output = [];
   let ri = 0;                            // current position in row
   let nr = 1;                            // asterisks in next row; always odd
   let lr = Math.floor(Math.sqrt(2*n+1))-1; // longest row
   for (let i=0; i<n; i++) {
     if (ri >= lr) {                
        output.push("\n");         // output end-of-row
        nr += 2;                   // each row has one extra `*` on each side
        ri = 0;
     } else if (ri >= ((lr - nr)/2) && ri < (lr - (lr - nr)/2)) {
        output.push("*");          // output actual brick
        ri ++;
     } else {
        output.push(".");          // output space
        ri ++;
     }
   } 
   return output.join("");
}

// test with 1 to 4 layers
for (let i=1; i<5; i++) {
  let n = (2*i)*i;
  console.log(n + "\n" + pyramid(n));
}

时间复杂度为 O(n) 的金字塔模式问题？

Pyramid pattern problem with O(n) Time Complexity?

algorithm

big-o

data-structures